ray

ray

매일의 HIGHLIGHT를 찾아서 ✨

[백준] 2110 공유기 설치 (C++)

Posted on Feb 19, 2021 #이진 탐색(Binary Search)   #Algorithm   #C/C++  

2110 | 공유기 설치

🙋‍♀️ 문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, …, xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

🙌 입출력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

🙋‍♂️ 예제 입출력

5 3
1
2
8
4
9

3

🚀 코드

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

int n = 0;
int c = 0;
vector<long long> v;

long long dist = 0;

void binary() {
	int lo = 1; // 수직선 범위의 시작과
	int hi = v[n - 1] - v[0]; // 끝
	// 그러니까 배열의 길이가 아닌 그 안에 들어있는 거리가 기준
	// 저번의 예산 문제에서도 배열의 길이로 접근했다가 틀렸었음
	int mid = 0;
	int cnt = 0;
	int gap = 0; // 간격
	while (lo <= hi) {
		mid = (hi + lo) / 2;
		// mid가 간격이 되는거임
		// 그래서 mid에 설치하고 mid만큼 떨어진 쪽에 또 설치
		// 설치하고 나면 거기서부터 다시 시작이니까 start를 v[i]로
		int start = v[0];
		cnt = 1; // 첫 번째 집에는 무조건 설치
		for (int i = 1; i < n; i++) {
			gap = v[i] - start;
			if (mid <= gap) {
				// 설치된 집에서부터 다음 설치까지의 gap이
				// mid보다 크거나 같아야함
				cnt++;
				start = v[i];
			}
		}
		if (cnt < c) {
			// 공유기 설치가 아직 안끝났으면 간격을 좁혀서 다시
			hi = mid - 1;
		}
		else {
			dist = mid;
			lo = mid + 1;
		}
	}
	return;
}

int main() {
	cin >> n >> c;
	long long x = 0;
	for (int i = 0; i < n; i++) {
		cin >> x;
		v.push_back(x);
	}
	sort(v.begin(), v.end());

	if (c == 2) {
		// c가 2이면 양 끝에 설치하는게 거리 최대
		cout << v[n - 1] - v[0];
	}
	else {
		binary();
		cout << dist;
	}
	return 0;
}

🌠 메모

이번 문제도 저번의 예산 문제와 마찬가지로 문제 풀이를 생각해 내는데 아주 많은 시간이 걸렸고 처음 풀이를 직접 생각했을 때는 완전 이상하게 접근했었다.

처음에는 이진탐색은 mid값을 기준으로 양쪽 중 하나를 선택하니까 공유기를 중간에 무조건 설치하고 왼쪽과 오른쪽은 다시 각각 재귀적으로 탐색을 하나보다 생각해서, (lo, mid-1)과 (mid+1, hi)의 범위에 대해 탐색을 또 했다.

이렇게 푸니까 예제 출력은 맞게 나왔지만 시간초과였다.. 아무리 생각해도 풀이가 떠오르지 않아 다른사람의 코드를 참고했지만, 이해하는데도 많은 시간이 걸린만큼 어려운 문제였다.

개인적인 의견으로는 아주 어려운 문제였기때문에 풀이를 따로 자세하게 적어놓겠다.

문제풀이

  • 이진 탐색을 진행할때 lo와 hi는 각각 집이 위치하는 수직선상의 거리의 최대와 최솟값이다. ([2, 7, 9, 11, 12]이면 lo는 2가 되는게 아니고 거리의 최소이니 무조건 1, hi는 12 - 2 = 10인 거리의 최대값)
  • lo와 hi로 결정되는 mid는 공유기를 설치할 간격이 된다. 처음엔 거리의 절반일것이고, 탐색을 진행하며 간격은 점점 촘촘하게 감소한다.
  • for문 안에서는 공유기를 설치한다. 공유기가 설치된 집(start)과 현재 위치의 집(v[i])의 거리 간격 gap을 계산해 이 값이 mid보다 크거나 같을 때 공유기를 설치한다.
  • 만약 mid가 3이라면, OXXXOXXXO와 같이 설치된다.
  • 아직 공유기 설치가 끝나지 않았다면(cnt < c) 간격을 좁혀서 다시 설치한다.

코드를 참고해서 문제를 풀었을 때에도 저번 문제와 같은 실수를 반복했는데, 바로 lo, hi값을 배열의 index로 설정한 것이었다. 이때문에 mid는 범위상의 모든 간격을 확인하지 못하고 배열의 값 안에서만 확인할 수 밖에 없었다.

두 번이나 같은 실수를 반복했으니, 다음 문제를 풀 때에는 보다 신경을 쓸 수 있을 것 같다!



# 카테고리