BOJ #2110 공유기 설치

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 2110. 공유기 설치

문제 풀이

이진 탐색 유형의 문제들 중 탐색 알고리즘 적용 방법이 단순 검색이 아니라 문제를 변형해서 적용할 수 있는 형태들에 대해 취약한 듯하다. 이 문제도 집들 간 간격에 대해 모두 탐색하지 않고 1개의 간격에 대해 $O(n)$의 시간이 소요되지만 정답 간격을 찾는데까지 $O(log\ n)$에 찾을 수 있다면 $O(nlog\ n)$에 문제를 해결할 수 있음을 보여준다.

집들 간 존재할 수 있는 최소 간격은 1이고 최대 간격은 마지막 집에서 첫 번째 집까지의 거리다. 그리고 탐색 간격은 (최대 + 최소) // 2가 된다. 탐색 간격은 적어도 만족해야 하는 최소한의 기준이므로 해당 간격을 최소한으로 잡고 설치했을 시 얼마나 넣을 수 있는가에 대한 함수만 작성하면 된다. 그리하여 설치할 수 있는 공유기의 대수와 문제에서 주어진 공유기 대수와 일치하는 간격들 중 최대값을 반환하면 되겠다.

• 문제로부터 진짜 공유기의 개수, 집들의 좌표를 입력받는다.

• 집들의 좌표를 정렬한다.

• 설치할 수 있는 공유기의 개수를 카운트하는 함수를 작성한다.

  첫집부터 공유기를 넣는다고 가정, 이전 좌표 + 간격 <= 다음 좌표 시 설치 가능 대수를 1 더하고 이전 좌표를 다음 좌표로 갱신한다.

• 이진 탐색 알고리즘을 적용한다.

  설치할 수 있는 공유기 개수가 요구량보다 작으면 최대 간격 갱신, 설치할 수 있는 공유기 개수가 요구량보다 크면 최소 간격 갱신을 하며 같은 경우엔 문제에서 요구하는 해답이 간격의 최대값이므로 최소 간격을 조정하는 경우에 등호를 넣고 별도의 버퍼에 탐색했던 간격을 저장하여 종결상황을 준비한다.

• 최소 간격과 최대 간격이 같아질 때까지 반복한다.

  최대 간격이 감소해서 종결되던 최소 간격이 증가해서 종결되던 버퍼에 while 문 종료 직전 조건을 만족했던 값이 버퍼에 저장되어 있는 상태다.

• 이후 저장된 버퍼의 값을 반환한다.

공유기 카운트 시 주의점

왜 첫 번째 집에 무조건 설치해야 하냐는 의문이 있을 수 있다. 이는 $a_1 + dist < a_2+dist$이기 때문에 최대한의 공유기를 설치하기 위함이다.(특정 탐색 간격으로만 설치하라는 제한이 없기 때문에 가능) 만약 $a_1 + dist$위치에 집이 없고 $a_2+dist$위치에 집이 있더라도 $a_1$에 설치 후 $a_2+dist$ 위치에 설치할 수 있음을 의미한다.

python 코드

import sys
input = sys.stdin.readline
 
N, C = map(int, input().split())
arr = []
for _ in range(N):
    arr.append(int(input()))
arr.sort()
 
def search(arr, C):
    def counting(dist):
        target = 0
        result = 1
        for i in range(1, len(arr)):
            if arr[target] + dist <= arr[i]:
                result += 1
                target = i
        return result
    min_dist, max_dist = 1, arr[-1] - arr[0]
    sol = 0
    while min_dist <= max_dist:
        mid_dist = min_dist + (max_dist - min_dist) // 2
        cnt = counting(mid_dst)
        if cnt >= C:
            min_dist = mid_dist + 1
            sol = mid_dist
        elif cnt < C:
            max_dist = mid_dist - 1
    return sol
print(search(arr, C))