[BOJ] 2110 : 공유기 설치 (C++)

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

2110번: 공유기 설치

걸린 시간 : 45분 44초

---

문제와 조건을 보고 한참을 생각하다,,,,, 결국 알고리즘 분류를 보았다.

매개 변수 탐색 문제이다. 실제 코딩테스트 등에서 많이 나올지는 모르는 문제이다. 너무 특수한 경우에만 적용 가능하고 기발한 생각으로 풀어야 하기 때문에 열심히 할 유형은 아니라고 생각된다.

 

매개 변수 탐색 (Parametric Search) 이란?

매개 변수 탐색 (Parametric Search) 란 최적화 문제를 결정 문제로 바꿔 푸는 것이다.

예를 들어 "어떤 길이의 막대가 소파 밑의 물건을 꺼낼 수 있을까?" 가 아니라, "이 길이 막대는 소파 밑의 물건을 꺼낼 수 있을까?" 로 바꿔서 생각해보자는 것이다.

전자의 질문은 개방형 질문이다. 답이 정수로 나올 수 있는 것이다.

이게 너무 어려울 경우에 후자의 질문을 생각해보자. 후자의 질문의 답은 참/거짓이다. 이 질문에 대한 답을 하기가 쉬울 수 있다.

즉 전자의 질문이 너무 어렵고 후자의 질문이 너무 쉽다면, 후자의 길이만 이분 탐색으로 바꿔가면서 결정하면 된다는 것이다.

 

즉, Parametric Search 는 답이 정수로 나오는 질문에 답해야 하는 경우에 그 질문을 "결정" 문제로 바꿔보았을 때, 문제 해결이 아주 쉬울 경우에 쓸 수 있는 것이다.

적용

이 문제의 경우, "어떤 공유기 사이의 길이가 C개의 공유기를 설치할 수 있게 하는가?" 가 아니라, "이 공유기 사이의 길이는 C개의 공유기를 설치할 수 있게 하는가?" 로 바꿔서 생각해보자는 것이다.

 

"이 공유기 사이의 길이는 C개의 공유기를 설치할 수 있게 하는가?" 질문은 답하기 쉬울까? (코드의 sol() 함수 부분)

예를 들어, 집들의 좌표가 1,3,6,9,12 일 때, 3 이라는 길이는 4개의 공유기를 설치할 수 있게 하는가? 에 대한 답변을 해보자.

첫 번째 집에 공유기를 설치하고 최소 3만큼의 길이를 떨어뜨려 다시 공유기를 설치한다. 이걸 반복하다 보면 설치 가능한 최대 공유기가 나온다.

하지만 이렇게 푼다면 첫 번째 집에 무조건 공유기를 설치하는 게 되어 버린다. 만약 첫 번째 집에 공유기를 설치하는 게 최적이 아닌 경우는 어떨까? 예를 들어서, 예시에서 3,6,9,12에 공유기를 설치하는 게 최적이라면, 첫 번째 집에 공유기를 설치한다는 가정이 잘못되었을 수 있다는 것이다.

이 문제는 귀납법으로 증명 가능하다. 두 번째 집부터 설치하는 경우가 최적일 경우를 생각해보자. 첫 번째 집에 공유기를 설치하면 첫 번째 집과 가장 가까운 집의 공유기를 철거하면 된다. 즉, 3,6,9,12 설치가 최적이어도 1에 공유기를 설치해야겠다고 한다면 3을 철거하고 1을 설치한 1,6,9,12도 최소 3만큼의 길이가 떨어져있다는 것이다. 따라서 첫 번째 집에 공유기를 냅다 설치한다고 가정해도 된다.

 

집들의 좌표를 정렬한 후, 길이의 후보가 될 수 있는 범위를 생각해본다. 1(st)부터 가장 먼 집끼리의 거리(en)일 것이다. st와 en 사이에 mid값을 정하고 이 값이 문제 조건을 만족하는지를 통해 이분탐색을 이어나간다.

만약, mid 값이 C개의 공유기를 설치할 수 있게 한다면 답을 갱신해주고 st = mid + 1; 을 실행해 더 긴 길이가 가능한지 알아본다. 아니라면 en = mid - 1; 을 실행해 더 짧은 길이는 가능할지 알아본다.

주의할 점

이런 이분 탐색 코드에서 중요한 것은 off-by-one 오류이다. 하나라도 잘못 된다면 무한 루프를 돌거나 아주 이상한 답이 나온다. 보통 off-by-one 오류를 겪는 곳은 다음과 같은 경우들이다.

• while (st < en)   VS   while (st <= en)
• mid = (st + en) / 2   VS   mid = (st + en + 1) / 2
• st = mid   VS   st = mid + 1
• en = mid   VS   en = mid - 1

하나하나 케이스를 생각해보면서 오류가 나지 않게 조심해야 한다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int N, C, ans;
int x[200001];

int sol(int k) {
	int cnt = 1, dist = 0;
	for (int i = 1; i < N; i++) {
		dist += x[i] - x[i-1];
		if (dist >= k) {
			cnt++;
			dist = 0;
		}
	}
	return cnt;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> C;
	for (int i = 0; i < N; i++) {
		cin >> x[i];
	}
	sort(x, x + N);
	int st = 1, en = x[N-1] - x[0];
	while (st < en) {
		int mid = (st + en + 1) / 2;
		int cand = sol(mid);
		if (cand >= C) {
			ans = mid;
			st = mid + 1;
		}
		else {
			en = mid - 1;
		}
	}
	cout << ans;
	return 0;
}