[백준]2110 - 공유기 설치 문제 풀이(파이썬,Python)

문제

2110번: 공유기 설치

 

들어가며

정말 머리가 터질 뻔한 느낌을 오랜만에 받은 문제이다.

들어가기 전에 이 문제가 이분 탐색이라는 것을 알고 있어서 최대한 이분 탐색을 사용해서 풀려고 했다.

근데 아무리 봐도 어디가 이분 탐색인지 안보였다.

답답해 미칠 뻔 했다.

아직까진 갈 길이 참 멀지 않나 싶다.. 화이팅

 

코드

l = list(map(int, input().split()))
n = l[0]
c  = l[1]

arr = []
for _ in range(n):
    arr.append(int(input()))
arr.sort()

result = 0

left = 1
right = arr[-1] - arr[0]

while left <= right:
    middle = (left + right) // 2
    cnt = 1
    last_installed = arr[0]
    for i in range(1,n):
        dist = arr[i] - last_installed
        if dist >= middle:
            cnt +=1
            last_installed = arr[i]
    if cnt >= c:
        left = middle+1
        result = max(result, middle)
    elif cnt < c:
        right = middle -1

print(result)

풀이

먼저, 좌표들을 정렬할 필요가 있다.

최대한 문제를 쉽게 만들기 위해서다.

(+ 이분 탐색을 위해서)

예시 입력만 봐도 좌표가 지멋대로 입력돼서 인접한 두 공유기 사이 거리를 구하기 힘들다는 것을 눈치챌 수 있다.

 

l = list(map(int, input().split()))
n = l[0]
c  = l[1]

arr = []
for _ in range(n):
    arr.append(int(input()))
arr.sort()

result = 0

이 부분은 입력 처리, 정렬, 그리고 결과값인 result를 초기화하는 부분이다.

 

left = 1
right = arr[-1] - arr[0]

while left <= right:
    middle = (left + right) // 2
    cnt = 1
    last_installed = arr[0]
    for i in range(1,n):
        dist = arr[i] - last_installed
        if dist >= middle:
            cnt +=1
            last_installed = arr[i]
    if cnt >= c:
        left = middle+1
        result = max(result, middle)
    elif cnt < c:
        right = middle -1

여기부터가 본 게임인 이분탐색이다.

 

먼저, 의문을 가져야할 것은 왜 이 문제는 이분 탐색으로 풀 수 있는가? 이다

여기서 탐색을 진행할 것은 정답인 가장 인접한 두 공유기 사이의 거리이다.

최대를 찾는 과정을 이분 탐색으로 진행한다.

말이 좀 이상하지만 한 줄 요약하면, 최소 거리의 최대값을 찾는 것이다.

그 과정 속에서 거리가 특정 값이 이상일 때, 공유기를 설치할 수 있는지 여부를 빠르게 검증할 수 있다.

예를 들어, 특정 좌표에 공유기를 설치할 수 있다면, 더 먼 곳에서도 가능성을 탐색할 수 있다. 반대로 특정 좌표에 공유기를 설치할 수 없다면, 더 작은 좌표로 탐색하면 되기 때문이다.

그렇기에 이분 탐색이 가능하다.

left = 1
right = arr[-1] - arr[0]

초기값을 설정하는 것이다.

left는 최소 거리인 1을, right는 정렬된 배열의 맨끝 집 좌표랑 첫 집 좌표 차이로 최대 거리이다.

 

	middle = (left + right) // 2
    cnt = 1
    last_installed = arr[0]

cnt는 공유기를 설치한 개수를 의미하고 last_installed는 제일 최근에 설치한 좌표를 의미한다.

이 부분을 보면 첫 번째 집을 이미 계산에 넣고 시작한다는 것을 알 수 있다.

첫 번째 집이라는 것은 가장 좌표가 작은 위치에 있는 집이다.

그렇기에 자연스럽게 탐샋 시 모든 경우를 파악할 수 있고, 최소 거리를 기준으로 하고 있기 때문에 결과에 영향을 미치지 않는다.

그래서 반드시 첫 번째 집을 선택함으로써 결과를 단순하게 바라볼 수 있게 된다.

last_installed를 따로 저장하는 이유는 후술할 예정이다.

 

for i in range(1,n):
    dist = arr[i] - last_installed
    if dist >= middle:
        cnt +=1
        last_installed = arr[i]

현재 두 공유기의 사이 거리를 middle로 고정했기 때문에, 하나씩 공유기를 놓아볼 수 있다.

그렇기 위해서 반복문을 돈다.

1부터 시작하는 이유는 이미 첫 번째 집을 반드시 선택하기로 했기 때문이고, last_installed를 따로 저장했던 것은 이전 설치한 위치를 파악함으로써 다음 위치에 공유기를 놓을 수 있는지 파악하기 위함이다.

만약 놓을 수 있다면, cnt += 1을 하고 last_installed를 갱신한다.

 

이렇게 진행하면 cnt이 문제에서 제시한 공유기의 개수 C와 같거나 다를 것이다.

그걸 처리해보자.

if cnt >= c:
    left = middle+1
    result = max(result, middle)
elif cnt < c:
    right = middle -1

 

만약 C보다 크거나 같을 경우, 거리를 더 높일 수 있다.

왜냐하면 거리가 남는다는 것이고, 우리는 최대 거리를 구해야하기 때문이다.

반대로 C보다 작다면, 공유기 개수를 줄여야 공유기 사이의 거리를 맞춰서 공유기를 놓을 수 있기 때문이다.

 

print(result)

이런 과정을 거치면 최종적으로 result엔 최대 거리가 들어가며, 출력하면 답을 구할 수 있다.