백준 1477 휴게소 세우기

문제 링크

링크 : https://www.acmicpc.net/problem/1477

문제

키 포인트

◆ parametric search 를 이용한다.

◆ can 함수에서 모든 구간을 x 길이 미만으로 만들기 위한 휴게소의 개수를 세어준 다음 개수가 m보다 크면 false 그렇지 않으면 true를 리턴

◆ l=INF,r=0 으로 두고 while(l-1 != r) 를 이용한 이분탐색 실시

시행착오

문제만 읽었을때 직관적으로 그리디하게 풀 수 있을것같은 느낌에 시도해봤다.
우선순위 큐에 휴게소 사이의 거리를 푸시한 다음 매번 가장 긴 거리를 반으로 나누어주며 답을 구하려 했지만..
이런식으로 접근하면 고속도로 10에 두개의 휴게소를 세울 때 2.5 2.5 5가 되므로 5가 반환된다..
실제로를 1/3 지점에 휴게소를 놓는 방법이 있으므로 그리디는 실패..

고민하다 알고리즘 분류에서 힌트를 얻어 해결했다.

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
#define INF 1001
int n, m, l;
vector<int> v;
vector<int> dist;
bool can(int x) {
	int cnt = 0;
	for (int i = 0; i < dist.size(); i++) {
		if (dist[i] > x) {
			if (dist[i] % x == 0) cnt += dist[i] / x - 1;
			else {
				cnt += dist[i] / x;
			}
		}
	}

	if (cnt > m) return false;
	return true;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> l;
	v.push_back(0);
	for (int i = 0; i < n; i++) {
		int t; cin >> t;
		v.push_back(t);
	}
	v.push_back(l);
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size() - 1; i++) {
		dist.push_back(v[i + 1] - v[i]);
	}



	int l = INF, r = 0;
	while (l - 1 != r) {
		int mid = (l + r) / 2;
		if (can(mid)) l = mid;
		else r = mid;
	}
	cout << l;
}

후기

연습이 더 필요하다.