백준 1477 휴게소 세우기

 

출처 : www.acmicpc.net/problem/1477

 

문제

다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다.

 

이 때 세울 수 있는 휴게소의 조건은 다음과 같다.

• 이미 휴게소가 있는 위치는 세울 수 없다.
• 고속도로의 마지막 점에 세울 수 없다.
• 정수 위치에만 세울 수 있다.

M개의 휴게소를 적절히 배치하여 휴게소가 없는 구간의 최댓값을 최소로 만들어라.

 

풀이

이 문제는 휴게소가 없는 구간의 최댓값을 이분 탐색으로 시뮬레이션하는 방법이 있긴 하나,

여기서는 우선순위 큐를 이용해 풀어보겠습니다.

 

우선 단순하게 생각해서 풀이를 떠올려보면, 당연히 휴게소가 없는 구간 중 가장 긴 구간의 중간 중간에

휴게소를 배치해야, 답이 최소로 나오게 됩니다.

 

예시)

그럼 가장 긴 구간의 정 중앙에 휴게소를 배치하고, 그 다음 긴 구간의 중앙에 배치하고.. 이런 식으로 m개의 휴게소를 배치하는 것이 최적일까요? 그렇지 않습니다.

만약 0~100 구간에서 휴게소를 4개 설치한다고 가정한다면

0, 33, 66, 100 구간에 설치하는게 위 3번 그림보다 최적이기 때문이죠. 참! 100에는 설치하지 못하니 99라 할게요.

 

따라서 이 문제는 길이 마다 나눈 횟수를 기록하는 것이 중요합니다. (그림에서 길이 100을 1이라 하면, 50은 2, 25는 3)

휴게소가 필요할 때마다 2씩 나누는 게 아니라, 특정 구간에서 n개가 필요하다면 전체 구간 / n-1 으로 n빵 해주는게 이득이기 때문이죠. 위에서 예로 든 0 ~ 100 구간도 100/3 으로 나눠주는게 최적이라는 의미입니다.

예를 들어 초기 거리 값이 100이라고 했을 때, 휴게소를 세운다면 100/2 = 50이 되고, 나눈 횟수는 2가 됩니다.

그 다음 휴게소를 세운다면 최장 구간이 50이므로 (50 * 나눈 횟수) 로 다시 전체 구간(100)을 구한 후

나눈 횟수를 하나 더 늘려 (전체 구간) / (나눈 횟수 + 1) 을 해주면 33.333...이 나오겠죠. (100 / 3)

 

이런식으로 문제를 해결해주면 되고, 가장 긴 구간을 O(1) 시간으로 구하기 위해 거리 값을 최대 힙에 모두 넣고 가장 위에 있는 원소를 꺼내 사용하면 되겠네요. 여기서 최대 힙 안에 나눈 횟수도 같이 넣어 줘야 계속 휴게소를 최적으로 세울 수 있겠죠?

 

추가로 길이가 홀수인 구간 k는 이등분 시(정수 구간에 배치할 때) (k/2), (k/2) + 1 로 나뉘므로 이 경우도 고려해

만약 정답에 소수점이 남아있다면 +1 올려줘야 합니다.

ex) 0 ~ 33 -> 0~17, 17~33 이지만, 33/2 = 16.5

 

소스 코드(.cpp)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	// (구간 길이, 나눈 횟수)
	priority_queue<pair<double, int> >pq;
	int n, m, l;
	cin >> n >> m >> l;
	vector<int>v(n);
	for (int i = 0; i < n; i++) cin >> v[i];
	sort(v.begin(), v.end());
	//휴게소 사이 구간 구하기
	for (int i = 0; i < n - 1; i++) {
		pq.push({v[i + 1] - v[i], 1});
	}
	//시작 점 ~ 첫 휴게소, 마지막 휴게소 ~ 끝 점 추가
	pq.push({ v[0], 1});
	pq.push({ l - v[n - 1], 1 });

	while (m--) {
		double dist = pq.top().first;
		int cnt = pq.top().second;
		pq.pop();
		//원래 길이로 변환 후, 더 나누어 준다.
		pq.push({ (dist * cnt) / (cnt + 1), cnt + 1 });
	}
	//소수점이 있는 경우 (홀수인 구간을 나눈 경우) + 1 해줘야 한다.
	// k가 홀수라면, (k/2), (k/2) + 1 두 가지 구간으로 나뉘기 때문
	double ans = pq.top().first;
	int tmp = (int)ans;
	if (tmp == ans) cout << tmp << "\n";
	else cout << tmp + 1 << "\n";
	return 0;
}