[BOJ] 휴게소 세우기 1477번

이분 탐색 문제는 많이 안 풀어봐서 그런지 항상 볼 때마다 접근 방법이 확실하게 생각나지 않는 것 같습니다. 힌트 주신 거에서 or를 보지 못하고 우선순위 큐와 이분 탐색을 어떻게 같이 써야 되나 고민하느라 이상한 쪽에서 시간을 보냈습니다.

접근 방법

1. 좌표 사이 값의 최대가 최소가 되도록 만들어야 했기 때문에 우선은 사이 값이 큰 수부터 처리를 해주어야 한다고 생각했습니다.(우선순위 큐 사용)

2. 테스트 케이스에 따라서 좌표와 좌표 사이 중간에 휴게소를 세웠을 때 최소가 되지만 백준에서 예시로 들어준 테스트 케이스와 같이 좌표와 좌표 사이에 여러 개의 휴게소를 세워야 하는 경우도 있습니다. 이 부분 처리를 어떤 식으로 해줘야 할지 모르겠어서 올려주신 풀이를 참고하였습니다.(굉장히 참신했던 것 같아요.)

소스 코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int main(void) {
	vector<int> vec;
	priority_queue<pair<double,int>> pq;
	int n, m, l;
	cin >> n >> m >> l;
	vec.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> vec[i];
	}

	sort(vec.begin(), vec.end());

	for (int i = 1; i < n; i++) {
		pq.push({ vec[i] - vec[i - 1],1 });
	}

	pq.push({ vec[0], 1 });
	pq.push({ l - vec[n - 1],1 });


	while (m--) {
		double dist = pq.top().first;
		int count = pq.top().second;
		pq.pop();
		pq.push({ (dist*count) / (count+1), count + 1 });
	}

	double ans = pq.top().first;
	int temp = (int)ans;
	if (ans == temp) cout << temp << '\n';
	else cout << temp + 1 << '\n';


}