<JUNGOL > 모자이크#1219

문제 : https://www.jungol.co.kr/problem/1219

무엇을 구하는 문제인가?

한변이 k인 정사각형 모양의 색종이 n개를 이용해 잘못칠해진 부분을 모두 가릴때, k의 최솟값을 구하는 문제이다.

​

해결 전략

k를 mid로 생각해 푸는 간단한 이분탐색 문제이다.

입력받을때, 잘못칠해진 부분의 높이는 최댓값만 필요하며, 그 최댓값은 low로 한다.

입력받은 좌표를 x기준 정렬 후, 탐색

​

알고리즘

1. 최대좌표의 값 mx, my를 입력받는다. 그 후 색종이의 수 n과 얼룩의 수 m또한 입력받는다.

2. m개의 얼룩의 x값을 저장, y는 최댓값만 저장하며 입력받는다.

3. low = maxy값, high = 최대 x값으로 한다.

4. x좌표를 정렬한다.

4. low가 high보다 작은동안 반복

-mid = (low + high)/2

-mid_res = mid가 k일때 사용한 색종이수

-mid_res가 n보다 작거나 같다면 -> high = mid - 1

-아니면 low = mid + 1

5. high + 1출력

​

※주의 할점

mid_res 가 n과 같아도 mid 출력 X -> 위조건을 만족하는 mid값이 여러개일때, 그중 최댓값이 출력될 수 있기 때문이다.

​

<소스코드>

#include <stdio.h>
#include <algorithm>

using namespace std;

long long mx, my, n, m, x[1010], y;

long long pand(long long w) {
	int i, j;
	long long ans = 1;
	w--;
	j = x[0] + w;
	for (i = 0; i < m; i++) {
		if (x[i] > j) {
			ans++;
			j = x[i] + w;
		}
	}
	return ans;
}

int main()
{
	int i, j;
	long long low = -2e9;
	scanf("%lld %lld %lld %lld", &my, &mx, &n, &m);
	for (i = 0; i < m; i++) {
		scanf("%lld %lld", &y, &x[i]);
		if (y > low) low = y;
	}
	sort(x, x + m);
	long long high = mx;
	while (low <= high) {
		long long mid = (low + high) / 2;
		long long mid_res = pand(mid);
		if (mid_res <= n) high = mid - 1;
		else low = mid + 1;
	}
	printf("%lld", high + 1);
	return 0;
}

 

 

​