[백준/BOJ] 백준 2539번 : 모자이크

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

2539번: 모자이크

 

이분 탐색을 통해 모든 잘못 칠해진 칸을 가리는 가장 작은 색종이의 크기를 구했는데, 이때 특정 크기의 색종이로 모든 잘못 칠해진 칸을 가릴 수 있는지 확인하는 방법은, 색종이를 도화지 밑변에 맞추어 붙인다는 것을 이용하여, 가장 작은 열 번호의 색종이부터 순서대로 가려서 모두 다 가릴 수 있는지 확인하는 방법으로 문제를 해결했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
int paper_cnt;
int error_cnt;
vector<pair<int, int>> errors; //(열번호, 행번호 순서로 저장)

bool check(int check_size) {

	//도화지의 밑변에 맞추어 붙인다는것을 이용
	//가장 왼쪽(가장 작은 열 번호)의 위치 부터 확인 한다

	int point = -1;
	int cnt = 0;

	for (int i = 0; i < errors.size(); i++) {

		int height = errors[i].second;

		if (height > check_size) { //위치가 너무 위에 있어서 밑변에 닿는 check_size 색종이로는 불가능 할 때
			return false;
		}

		if (point == -1) { //기준 지점이 정해지지 않았을때 
			//errors[i]의 열을 가장 왼쪽으로 하고 아래는 밑변에 닿는 색종이라고 생각
			point = errors[i].first;
			cnt++;

			continue;
		}

		if (point + check_size - 1 < errors[i].first) { //해당 기준 지점으로는 불가능 해서 새로운 기준점의 색종이가 필요할 때
			point = errors[i].first;
			cnt++;

			if (cnt > paper_cnt) {
				return false;
			}
		}
	}

	return true;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;
	cin >> paper_cnt;
	cin >> error_cnt;

	for (int i = 0; i < error_cnt; i++) {
		int x, y;
		cin >> x >> y;

		errors.push_back(make_pair(y, x));
	}

	//열 번호로 정렬
	sort(errors.begin(), errors.end());

	int left = 1;
	int right = 1000000;
	int result = -1;

	while (left <= right) {
		int mid = (left + right) / 2;

		if (check(mid)) {
			result = mid;
			right = mid - 1;
		}

		else {
			left = mid + 1;
		}
	}

	cout << result;

	return 0;
}