[백준알고리즘] 2110번: 공유기 설치 -Python

[백준알고리즘] 2110번: 공유기 설치 -Python

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

2110번: 공유기 설치

이분 탐색 문제로 해결할 수 있는 문제이다. 처음에는 N분탐색을 해야하는 문제인지 뭐로 해야하는 문제인지 갈피를 못 잡았었다.... 아직 알고리즘 분류를 모르면 수월하게 해결할 수 있는 능력이 부족하다.

 

이 문제를 Binary Search로 해결하기 위해서는 공유기 간의 거리를 이분 탐색의 탐색 대상으로 생각하면 된다. 즉, 어디에 놓을지를 먼저 생각하는 것이 아니라 얼만큼 떨어진 곳에 두어야 하는지가 먼저 고려되어야 하는 부분이다.

 

주어진 입력 예시를 보게되면 5개의 집, 3개의 공유기가 존재한다. 이때 우리는 공유기간의 최소 거리가 x일때 5개의 집에 3개의 공유기를 설치할 수 있는가를 살펴보면 된다. 예시의 집 좌표를 정렬하게 되면 1 2 4 8 9 이다. 여기서 간단하게 먼저 가장 끝 쪽에 위치한 두 개의 집좌표의 거리를 2로 나누면 4가 된다. 이 거리 4가 공유기간의 최소 거리일때 공유기를 3개 배치할 수 있는가 생각해보면 된다.

 

4가 최소 거리일때 3개의 공유기를 설치할 수 있다면 4를 가장 큰 최소 거리로 저장하고 더 탐색을 위해 가능한 거리의 범위는 5(4 + 1) ~ 8(9 - 1) 가 된다. 그럼 여기서는? 마찬가지로 5와 8의 중간값인 6(또는 7)로 반복해서 진행하면 된다. 이러한 형태는 이분 탐색의 형태가 된다.

 

그렇다면 반대로 하는 것도 생각할 수 있다. 4가 최소 거리가 되지 못한다면 가능한 최소 거리의 범위는 집끼리 최소 1씩 떨어져있기 때문에 1 ~ 3(4 - 1)이 될 것이다.

 

하지만 여기서 하나 더 나아갈 수 있는 부분은 안 해도 되지만, 처음 가능한 범위의 maximum값을 지정해줄 때이다. C개를 설치하기 위해서는 사실 전체 거리의 각 등분의 길이가 최소 길이보다 긴 C-1등분으로 나눌 수 있으면 된다. 따라서 C-1로 나눈 몫이 최소 거리의 최댓값일 확률이 크다. 하지만 탐색으로 정확히 찾기 위해서는 그것보다 하나 큰 값을 maximum으로 지정해주면 된다. 이 부분은 설명이 헷갈리는 것 같지만.. 좌표를 n등분 내면 n+1개의 경계가 생기는 것을 생각하면 될 것 같다......? 그리고 직접 계산을 해보면 될 것 같다.

 

예를 들어 최소 좌표가 2, 최대 좌표가 13인 집들이 여러 채 존재한다고 했을 때 3개의 공유기를 놓고 싶다고 해보자. 이때 (13-2)//2 = 5 가 되는데, 5가 최소 거리라고 하면 2, 7, 12로 가능할 수도 있게 된다. 하지만 5 + 1 = 6 을 최소 거리라고 생각하면 2, 8, 14 로 불가능하기 때문에 안전성을 위해 6을 maximum으로 잡아두게되면 잘못 구할 위험도 없으며 검사할 범위도 줄어들게 된다.

 

import sys

sys.setrecursionlimit(10**9)

N, C = map(int, sys.stdin.readline().split())
ap = [int(sys.stdin.readline()) for _ in range(N)]
ap.sort()

answer = 0
def solve(minimum, maximum):
    if minimum > maximum:
        return
    
    dist = (maximum + minimum) // 2
    cnt = 1
    target = 0
    
    for idx in range(N):
        if ap[idx] >= ap[target] + dist:
            cnt += 1
            target = idx
    
    if cnt >= C:
        global answer
        answer = max(answer, dist)
        solve(dist + 1, maximum)
    else:
        solve(minimum, dist - 1)


solve(1, (ap[-1] - ap[0])//(C - 1) + 1)
sys.stdout.write(str(answer))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다