[백준, G3, 2539] 모자이크

0. 문제 링크

https://www.acmicpc.net/problem/2539

2539번: 모자이크

---

1. 문제 핵심

1. 사용되는 색종이는 모두 크기가 같고 정사각형 모양이다.
2. 색종이 크기는 한 변의 길이로 나타내며, 원하는 크기의 색종이는 모두 구할 수 있다.
3. 모든 색종이는 반드시 도화지의 밑변에 맞추어 붙인다. 이때 색종이를 겹쳐서 붙일 수 있다.
4. 1, 2, 3번 조건의 설명은 조금 간단히 되어있어서 전 이런 식으로 이해를 했습니다.
   1. 색종이는 도화지보다 커도 상관 없다.
   2. 도화지보다 커도 상관없기 때문에 도화지의 범위에 영향을 받지 않는다.
   2. 도화지 밑변에 붙어야하고 정사각형이기 때문에 색종이의 최소 길이는 잘못된 모자이크 중 가장 높은 것과 같다.
   
   

---

2. 문제 접근

1. 행의 개수와 열의 개수가 100만개 이하이고 가장 작은 색종이의 크기를 출력하라고 해서 이분탐색 문제임을 알았습니다.
2. 색종이의 최소 cm를 구하는 것이 목적이기 때문에 이분탐색의 대상은 색종이의 길이입니다.
   색종이의 최소 길이는 틀린 모자이크의 최대 높이이고 최대 높이는 틀린 모자이크의 최대 너비입니다.
   색종이의 중앙값을 설정했다면 해당 cm로 몇 개의 색종이를 사용하는지 계산해줍니다.
   만약 해당 길이로 필요한 색종이의 수를 계산했을 때 색종이를 더 많이 사용할 경우 짧다는 것을 의미하기 때문에 left = mid + 1 로 길이를 늘려줍니다.
   색종이를 더 적게 사용한 경우 길이가 긴 것이기 때문에 right = mid - 1 로 길이를 줄여줍니다.
   정확히 필요한 색종이의 개수만큼 사용한 경우 해당 길이를 정답 변수에 저장하고 더 짧은 길이로도 가능한지 확인하기 위해 길이를 줄여줍니다.

---

3. 코드 분석

1.  

---

4. 베스트 코드 분석

1.  

---

5. 코드

import java.io.*;
import java.util.*;

class Main {
	static class reader {
		int bufferSize = 1 << 18;
		byte[] buffer = new byte[bufferSize];
		DataInputStream dis = new DataInputStream(System.in);
		int bufferPointer = 0, bytesRead = 0;

		byte read() throws IOException {
			if (bufferPointer == bytesRead) {
				bytesRead = dis.read(buffer, bufferPointer = 0, bufferSize);
				if (bytesRead == -1)
					buffer[0] = -1;
			}
			return buffer[bufferPointer++];
		}

		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ') {
				c = read();
			}
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}
	}

	public static void main(String[] args) throws IOException {
		reader br = new reader();
		int y = br.nextInt();
		int x = br.nextInt();

		boolean[] arr = new boolean[x + 1];

		int paper = br.nextInt();
		int wrong = br.nextInt();

		// 가장 높은 모자이크를 구하기(최소 종이의 길이가 됨)
		int maxHeight = 0;
		int wrongY, wrongX = 0;
		for (int i = 0; i < wrong; i++) {
			wrongY = br.nextInt();
			wrongX = br.nextInt();
			maxHeight = Math.max(maxHeight, wrongY);
			arr[wrongX] = true;
		}
		// left: 최소 종이는 틀린 모자이크 중 최대Y, right: 최대 높이, 최대 X 중 더 큰 것
		// 겹칠 수 있기 때문에 전체 불량 모자이크를 덮을 수 있는 사각형이라면 그냥 한 자리에서 중복 겹치기
		int cnt, answer = Integer.MAX_VALUE, left = Math.min(maxHeight, wrongX), right = Math.max(maxHeight, wrongX),
				mid = 0;

		while (left <= right) {
			cnt = 0;
			mid = (left + right) / 2;
			// 몇 장 가능한지 계산
			for (int i = 1; i <= x; i++) {
				// 불량 모자이크가 있는 열
				if (arr[i] == true) {
					cnt++;
					i += mid - 1;
				}
			}
			// 종이 개수와 동일하다면 길이를 줄여야 함.
			if (cnt == paper) {
				right = mid - 1;
				answer = Math.min(answer, mid);
			}
			// 더 많은 종이를 사용한 경우
			else if (cnt > paper) {
				left = mid + 1;
			}
			// 종이를 더 적게 사용한 경우
			else {
				right = mid - 1;
			}
		}
		if (answer == Integer.MAX_VALUE)
			System.out.println(maxHeight);
		else
			System.out.println(answer);
	}
}