BOJ(C++) / 백준 2110 : 공유기 설치

백준 2110 : 공유기 설치

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

2110번: 공유기 설치

 

코드

//백준 2110 공유기 설치
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, C;
	cin >> N >> C;
	vector <int> house;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		house.push_back(num);
	}

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

	int dis = 0;
	int left = 1; //공유기 사이 거리 최소
	int right = house[N - 1] - house[0]; // 공유기 사이 거리 최대
	while (left <= right) {
		int count = 1;
		int mid = (left + right) / 2;
		int cur = house[0];
		for (int i = 1; i < N; i++) {
			if (house[i] - cur >= mid) {
				cur = house[i];
				count++;
			}
		}
		if (count >= C) {
			dis = mid;
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}

	cout << dis << "\n";

	
	return 0;
}

 

설명

이분 탐색으로 풀어야 하는 문제이다.

입력받은 집의 위치를 오름차순으로 정렬한다.(이분탐색은 무조건 오름차순으로 정렬되어 있어야 한다.)

left를 공유기 사이 최소 거리인 '1', right를 공유기 사이 최대 거리인 '마지막 집 - 처음 집' 으로 둔다.

mid는 공유기 사이 거리를 나타낸다. 반복문을 통해 mid이상 거리를 가지는 공유기의 개수를 구한다.

mid이상 거리를 가지는 공유기의 개수가 원하는 설치 개수와 같거나 클 때를 구한다.

 

고찰

처음 해결법이 떠오르지 않았다.. 이분 탐색인가?라는 생각은 해봤지만 이분 탐색으로 접근하는 방법을 몰라서 결국 구글링 해서 문제를 해결할 수 있었다. 항상 이분 탐색은 너무 어렵다.ㅠㅠ 문제를 보고 어떤 알고리즘으로 접근해야 할지 항상 막막하다. 더 연습하면 문제를 더 잘 풀 수 있지 않을까 생각한다.

이번 문제는 다음에 꼭 다시 풀어봐야겠다.

 

난이도

Gold 5