[백준] 2110번: 공유기 설치

📌 문제

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

📌 설명

이분 탐색으로 최적의 인접 공유기 사이 거리를 구해야 하며, 이를 parametric search 라고 한다. 공유기 사이 거리로 가능한 값 중, 가장 작은 값은 1이고, 가장 큰 값은 가장 멀리 떨어진 두 집 간 거리일 것이다.

첫 번째 공유기는 첫 번째 집에 설치하는 것이 가장 최적이다. 이에 대해 그리디하게 접근해보자. 첫 번째 공유기를 첫 번째 집에 설치하게 되면 그 뒤에 설치될 공유기들이 배치될 수 있는 영역이 최대가 된다. 만약 첫 번째 공유기를 두 번째 또는 그 이후 집에 배치한다고 가정해보자. 그렇다면 해당 공유기 기준 왼쪽 영역은 버려지며, 다른 공유기들이 배치될 오른쪽 공간은 더 좁아지게 된다.

이분 탐색을 통해 문제 조건에 부합하는 공유기 거리를 구해도 탐색은 계속 진행되어야 한다. 현재 구한 값보다 더 큰 인접 공유기 사이 거리가 존재할 수 있기 때문이다. 이에 대한 구현이 l = m + 1 이다.

문제 조건에 부합하는 공유기 사이 거리를 구했을 때, 처음에는 ans = max(ans, m) 으로 답을 구했다. 그러나 매개 변수 탐색 특성 상, 조건에 부합하는 경우 m의 값은 계속 증가한다. 따라서 ans = m 으로 작성해도 무방하다.

📌 코드

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

using namespace std;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);

	int n, c;
	cin >> n >> c;

	vector<int> v;
	for (int i = 0;i < n;i++) {
		int x;
		cin >> x;
		v.push_back(x);
	}

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

	int l = 1; // 공유기 사이 거리 최소값
	int r = v[n - 1] - v[0]; // 공유기 사이 거리 최대값
	int ans = 0; // 인접 공유기 사이 최대 거리

	while (l <= r) {
		int m = (l + r) / 2; // 인접 공유기 사이 최대 거리 후보값

		// 첫 번째 집에는 반드시 공유기를 설치한다.
		int cnt = 1;
		int s = v[0]; // 직전 공유기 설치 위치
		for (int i = 1;i < n;i++) {
			if (v[i] - s >= m) {
				cnt++;
				s = v[i];
			}
		}

		if (cnt >= c) {
			ans = m;
			l = m + 1;
		}
		else {
			r = m - 1;
		}
	}

	cout << ans;
}

---

import sys

n, c = map(int,sys.stdin.readline().split())

arr = [int(sys.stdin.readline()) for _ in range(n)]
arr.sort()

l=0 # 공유기 사이 거리 최소값
r=arr[-1]-arr[0] # 공유기 사이 거리 최대값
ans=0 # 인접한 공유기 사이 최대 거리

while l<=r:
    m=(l+r)//2 # 공유기 간 최대 거리 후보값
    
    # 첫 번째 집에는 공유기를 반드시 설치한다.
    prev=arr[0] # 직전에 공유기를 설치한 잡
    cnt=1 # 설치한 공유기의 수
    for i in range(1, n):
        if arr[i]-prev>=m:
            cnt+=1
            prev=arr[i]

    if cnt>=c:
        ans=m
        l=m+1
    else:
        r=m-1

print(ans)