[백준]2539: 모자이크 - JAVA

[백준]2539: 모자이크

2539번: 모자이크

풀이

🪑 조건을 만족하는 가장 작은 수를 구하는 문제!! 바로 이분탐색 문제이다.

 

문제의 조건을 보자.

• 모든 색종이의 크기는 모두 같고 정사각형이다.
• 색종이 크기는 한 변의 길이이다. 원하는 크기의 모든 색종이가 존재한다.
• 모든 색종이는 밑변에 맞추어 붙인다. 또한 겹쳐 붙일 수 있다.
• 주어진 색종이이 장수로 이러한 조건에 맞춰 잘못 칠해진 칸을 가릴 수 있는 가장 작은 색종이의 크기를 구한다. 

 

 

🔧 풀이 과정을 정리해 보자!

1. 색종이의 크기를 기준값으로 이분탐색을 진행한다.
2. 해당 크기로 주어진 만큼의 색종이를 사용하여 잘못 칠해진 칸을 가릴 수 있는지 확인한다.
3. 가릴 수 있다면 더 작은 색종이를 사용해 본다.
4. 가릴 수 없다면 더 큰 색종이를 사용해 본다.

 

🔹 색종이의 크기를 기준값으로 이분탐색을 진행한다.

- 이때 색종이 크기의 범위는 어떻게 정할지 생각해 보자.

- 제일 작은 색종이는 한 변이 1인 색종이가 될 것이다. 그럼로 left값은 1로 설정했다.

- 제일 큰 색종이는 가로, 세로 길이 중에 더 큰 값을 같는 길이 만큼이 될 것이다. Math.MAX함수를 사용하여 행과 열 중에 더 큰 값으로 설정해 주었다.

 

🔹 해당 크기로 주어진 만큼의 색종이를 사용하여 잘못 칠해진 칸을 가릴 수 있는지 확인한다.

- 잘못 칠해진 칸의 좌표들을 미리 ArrayList로 받아 y좌표 순서대로 오름차순 정렬시켜 놓았다.

- 이전에 색종이를 붙여주었던 위치를 확인하며 새로 색종이를 붙여야 한다면 색종이 개수를 늘려주었다.

- 색종이는 밑면에 닿게 붙여야 하므로 x좌표의 위치가 붙일 색종이의 한 변의 길이를 넘는다면 false를 반환하도록 하였다.

- 또한 붙이는 색종이 개수가 주어진 색종이 수보다 커져도 false를 반환하도록 하였다.

 

🔹 가릴 수 있다면 더 작은 색종이를 사용하고 가를 수 없다면 더 큰 색종이를 사용한다.

- 가릴 수 있다면 더 작은 색종이를 사용해도 가릴 수 있는지 확인하는 과정이 필요하다.

- 가릴 수 없다면 더 큰 색종이를 사용하여 가릴 수 있는지 확인하는 과정이 필요하다. 

 

코드

import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        int r = scan.nextInt();
        int c = scan.nextInt();
        int confetti = scan.nextInt();
        int k = scan.nextInt();
        
        ArrayList<Node> list = new ArrayList<>();
        for(int i = 0; i < k; i++) {
            list.add(new Node(scan.nextInt(),scan.nextInt()));
        }
        Collections.sort(list); //y좌표 순서대로 오름차순
 
        int left = 1;
        int right = Math.min(r, c); //가로, 세로 길이중 더 큰 값
        while(left <= right) {
            int mid = (left + right) / 2;
 
            if(can_blind(mid, confetti, list)) {
                right = mid - 1;
            } else left = mid + 1;
        }
        System.out.println(left);
    }
 
    public static boolean can_blind(int m, int confetti, ArrayList<Node> list) {
        int count = 0;
        int pre = 0;
        for(int i = 0; i < list.size(); i++) {
            Node current = list.get(i);
            if(current.x > m) return false;// 밑면에 닿게 붙였을 때 닿을 수 없는곳.
            if(pre == 0 || pre + m <= current.y) {
                pre = current.y;
                count++;
                if(count > confetti) return false;
            }
        }
        return true;
    }
 
    public static class Node implements Comparable<Node> {
        int x;
        int y;
 
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
 
        @Override
        public int compareTo(Node n) {
            return this.y - n.y;
        }
    }
}