[KOI 2007 초등부 3번] 백준 2539번 모자이크 문제 풀이

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

2539번: 모자이크

한국정보올림피아드 2007년도 초등부 3번문제이자 백준 2539번 문제 "모자이크"문제 풀이입니다.

 

2007년도때 초등부 문제는 3문제만 나왔네요. 마지막 문제 3번 문제입니다.

 

문제 분석

2차원 행렬칸에 구멍이 난 녀석이 있고, 정사각형 색종이로 이들을 모두 가려야 합니다.

 

정사각형 색종이의 개수는 정해져 있고, 겹쳐서 덮어도 됩니다. 정사각형 색종이의 최소 크기를 구하는 문제입니다.

 

뭔가 나름 어려운 문제 일 수도 있는데, 한 가지 조건 덕에 난이도가 꽤 낮아진 감이 있습니다.

 

바로 "모든 색종이는 반드시 도화지의 밑변에 맞추어 붙인다." 라는 조건이죠. 밑 변에 맞추어서 붙여야 한다는 조건이 있습니다.

 

 

행과 열 개수는 100만 미만이라고 하니, 이들을 모두 2차원 배열로 잡기는 조금 무리가 있어 보입니다.

 

알고리즘 구상

일단 모든 색종이는 도화지의 밑변에 맞추어 붙어야 한다는 조건 때문에, 구멍이 난녀석의 y좌표가 가장 높은 녀석을 커버할 수 있어야 합니다.

 

따라서 색종이의 크기 최소값은, 가장 큰 y좌표 값 보다는 같거나 커야 합니다.

 

그리고 모든 점을 덮을 최소 색종이 크기를 알아내야하는데, 이는 파라메트릭 서치로 풀 수 있습니다.

 

문제를 다음과 같이 환원합니다.

 

//(f(x)//) => 색종이 크기가 x일 때 주어진 개수의 색종이로 모든 점을 덮을 수 있는가?

 

만약 크기가 x일때 모두 덮을 수 있다면, 당연히 x+1의 크기로도 덮을 수 있겠지요.

 

만약 y크기로 덮을 수 없다면, y-1의 크기로도 덮을 수 없습니다.

 

이러한 성질을 이용하여 파라메트릭 서치(바이너리 서치)로 풀 수 있습니다.

 

 

//(f(x)//)는 그리디하게 구할 수 있습니다.

 

구멍의 x좌표들만 모아놓은 상태에서, 처음 만나는 점을 색종이의 가장 왼쪽 변에 맞게 놓는다고 치고,

 

지금 놓여진 색종이의 오른쪽 변을 넘어가면 새로운 색종이를 덮는 식으로, 총 색종이가 몇 장 필요한지 알아내서

 

주어진 색종이 개수로 덮을 수 있는지를 확인하면 됩니다.

 

따라서 //(f(x)//)는 //(O(N)//)만에 구할 수 있고, 여기서 //(N//)는 잘못 칠해진 색종이 칸의 개수이므로 1000이 됩니다.

계산량은 총 //(1000 * lg1000000//)이므로, 쉽게 구할 수 있습니다.

 

코드

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
vector<int> arr;
int need(int width) {
	// 색종이 폭이 width일때, 다 덮기 위해 필요한 종이의 수
	int prev = -1;
	int ret = 0;
	for (int pos : arr) {
		if (prev == -1) {
			//처음 종이를 놓는 경우, [prev, prev+width) 까지 커버 가능
			prev = pos;
			ret++;
		}
		else if (prev + width <= pos) {
			prev = pos;
			ret++;
		}
	}
	return ret;
}
int main() {
	int row, col, num_paper, num_hole;
	int max_height = 0;
	cin >> row >> col >> num_paper >> num_hole;
	for (int i = 0; i < num_hole; i++) {
		int x, y; //행, 열
		cin >> x >> y;
		max_height = max(max_height, x);
		arr.push_back(y);
	}
	sort(arr.begin(), arr.end());
	int l = max_height;
	int r = 1000000; //range = [l, r]
	while (l < r) {
		int m = (l + r) / 2;
		if (need(m) <= num_paper) {
			//가능한 경우
			r = m;
		}
		else {
			l = m + 1;
		}
	}
	cout << l << endl;
	return 0;
}