[백준] 1508번 레이스 - C++

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

1508번: 레이스

문제

세준이는 세준항공으로 돈을 무지막지하게 번 뒤, 레이스 대회를 개최했다. 레이스 트랙은 길이가 N인 직선이다.

세준이는 심판 M명을 적절한 곳에 배치시키려고 한다. 심판은 아무 곳에나 배치시킬 수 있지 않다. 심판은 미리 정해진 K개의 곳에만 위치할 수 있다.

세준이는 심판을 배치할 때, 가장 가까운 두 심판의 거리를 최대로 하려고 한다.

심판을 어디에 배치시켜야 할지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M, K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, M은 K보다 작거나 같다. 또, K는 2보다 크거나 같고, 50보다 작거나 같다. 둘째 줄에 심판이 있을 수 있는 K개의 위치가 주어진다. K개의 위치는 N보다 작거나 같은 자연수 또는 0이며, 오름차순으로 주어진다.

출력

첫째 줄에 심판을 어떻게 배치시켜야 가장 가까운 심판의 거리가 최대가 될 것이지 출력한다. 출력할 때는 예제와 같이 심판을 세울 곳에는 1을, 세우지 않을 곳에는 0을 출력한다. 만약 정답이 여러개일 경우에는 사전순으로 가장 늦는 것을 출력한다.

---

 

    구해야하는 것은 '심판의 거리가 최대가 되는 것'이다. 따라서 매개변수를 심판들 사이의 거리로 두어 길이를 조정해가며 최댓값을 찾겠다고 생각할 수 있다.

    s = 1 , e = 시작점~ 끝점 으로 두어 h = (s+e) / 2의 거리가 최소가 되도록 심판을 배치하여 이 값이 m 보다 많이 등장했다면 h 값을 저장한다 그다음 s를 증가시켜 심판 사이의 거리가 증가하여도 가능한지 확인한다. 그렇지 않다면 e를 감소시켜 심판 사이의 거리를 줄여보도록 한다. 마지막으로 m보다 많이 배치한 거리 h의 값이 심판들의 최대 거리가 된다. 그 이유는 m보다 많은 경우 h 값을 저장하고 s 값을 늘려 결국 h 값이 증가하게 된다. 즉, 나중에 저장된 h 값일수록 값이 크다는 것이다.

    사전 순으로 가장 늦는 것으로 출력하라는 것은 1010 과 1001 이 둘 다 가능할 경우 1010을 출력하라는 말로 앞에서부터 착실하게 채워나가면 된다. 따라서 맨 앞자리에는 심판을 무조건 배치하고 그다음 위에서 구해놓은 h 값으로 이전 1과의 거리가 h 보다 크거나 같아지면 1을 아니면 0을 출력하면 된다.

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

int n, m, k,s,e,h,pre,cnt,res=-1;
int arr[51];

int main() {
	cin >> n >> m >> k;
	for (int i = 0; i < k; i++) cin >> arr[i];
	s = 1; e = arr[k-1]-arr[0];
	while (s <= e) {
		h = (s + e) / 2;
		pre = arr[0]; cnt = 1;
		for (int i = 1; i < k; i++) {
			if (arr[i] - pre >= h) {
				pre = arr[i];
				cnt++;
			}
		}
		if (cnt >= m) {
			res = h;
			s = h + 1;
		}
		else e = h - 1;
	}
	pre = arr[0]; cout << 1; cnt = 1;
	for (int i = 1; i < k; i++) {
		if ( (arr[i] - pre >= res ) && (cnt < m)) {
			cout << 1;
			cnt++;
			pre = arr[i];
		}
		else {
			cout << 0;
		}
	}
	return 0;
}

---

    처음 봤을때 '공유기 설치' 문제와 동일한 문제인 줄 알고 빠르게 풀려고 하였으나 틀렸습니다가 계속 나왔다. 아무리 봐도 안 보여 놔두고 오늘 다시 풀었는데 저번 고민이 무색하게 몇 분 만에 발견하게 되었다. 문제는 공유기 설치 문제는 m의 제한이 없었고 이번 문제는 존재하여 1을 배치할 때 m개만큼 배치하였다면 이후에는 0만 배치하는 것을 놓치고 있었다. 또한 처음 것은 무조건 출력이기 때문에 첫 cnt를 1로 시작했어야 했다. 안 풀린다고 흥분하지 말고 천천히 살피면 답은 나오는 것 같다. 역시 코드는 거짓말하지 않는다!