C++ / 백준 / 2110 / 공유기 설치

문제

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

2110번: 공유기 설치

문제풀이

이분 탐색을 하고 한번 진행하는 동안 반복문을 돌려 첫 집부터 마지막 집까지 돌면서 이전 공유기 설치된 집 +mid값 보다 더 긴 거리의 집이 있으면 공유기를 설치하는 식으로 문제를 풀어야 한다.

	for (idx; idx < N; ++idx)
		cin >> house[idx];	
	sort(house.begin(), house.end());

이 문제에서는 집을 거리순으로 정렬을 꼭 해야 이분 탐색을 할 수 있다.

	while (left <= right) {
		int iptime_cnt = 1;
		int pre_idx = 0;
		int mid = (left + right) / 2;
		for (idx = 1; idx < N; ++idx) {
			if (house[idx] - house[pre_idx] >= mid) {
				pre_idx = idx;
				iptime_cnt++;
			}
		}
		if (iptime_cnt >= C)
			left = mid + 1;
		else right = mid - 1;
	}

첫 집에는 무조건 설치를 해야 한다. 그래야 최장거리가 나올 수 있기 때문이다.

첫 집에 공유기를 설치했으므로 pre_idx를 0으로 두고 반복문을 돌린다.

현재 위치의 집 - 이전 공유기 설치한 집의 거리가 left+right를 더한고 반으로 나눈 mid값보다 크다면 공유기를 설치하고, pre_idx를 idx로 변경한다.

공유기가 목표했던 개수만큼 설치했거나 더 많이 설치했을 경우 간격을 더 크게 설치할 수 있는 경우가 있으므로 left를 mid+1로 두어 mid값을 정할 때 조금 더 오른쪽으로 가서 mid값을 더 크게 (공유기 설치 간격을 크게)한다.

C보다 적을 경우 right값을 mid-1로 변경하여 공유기를 설치한 집 간격을 줄인다.

이를 반복하고 right값을 출력한다.

 

 

코드

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N = 0, C = 0;
	int idx = 0;	

	cin >> N >> C;
	
	vector<int>house(N, 0);
	for (idx; idx < N; ++idx)
		cin >> house[idx];	
	sort(house.begin(), house.end());

	int left = 0, right = house[N-1];

	while (left <= right) {
		int iptime_cnt = 1;
		int pre_idx = 0;
		int mid = (left + right) / 2;
		for (idx = 1; idx < N; ++idx) {
			if (house[idx] - house[pre_idx] >= mid) {
				pre_idx = idx;
				iptime_cnt++;
			}
		}
		if (iptime_cnt >= C)
			left = mid + 1;
		else right = mid - 1;
	}
	cout << right;	
}