[백준] 2110 공유기설치 (Python)

문제이해

집 N개 중 C개를 골라 공유기를 각각 하나씩 설치한다.
설치된 공유기들 중 가장 인접한 두 공유기 사이의 거리가 최대여야 한다.

접근

풀기 전에 알고리즘 분류를 봐버렸기 때문에 이분탐색으로 풀어야할 것을 미리 알고 시작했다.
문제는 무엇을 기준으로 두고 이분탐색을 할 것인가 였는데 ...
이분탐색 문제에서는 그 기준에 대한 힌트를 문제의 출력값에서 찾을 수 있다.

고로 가장 인접한 두 공유기 사이의 최대 거리를 기준으로 이분탐색을 했다.

틀린 코드

import sys

input = sys.stdin.readline

n, c = map(int, input().split())
house = [int(input()) for _ in range(n)]

house.sort()


# 공유기 간 거리의 범위를 (1, house[n-1]-house[0]+1)로 설정
srt = 1
end = house[n - 1] - house[0]

# 가장 인접한 두 공유기 사이의 최대 거리에 대한 이분탐색
while srt <= end:

    # 설치할 공유기가 2개일 때는 최대값을 바로 반환
    if c == 2:
        dist = house[n - 1] - house[0]
        break

    dist = (srt + end) // 2

    flag = 0  # dist값을 기준으로 c개의 공유가 설치가능하나, 최대가 아닐 때를 체크하기 위함
    cnt = 1
    h = house[0]

    # 각 공유기 간 거리가 dist보다 같거나 클 때 설치 가능한 공유기 count
    for i in range(1, n):
        if house[i] - h >= dist:
            h = house[i]
            cnt += 1

            if house[i] - h == dist:
                flag = 1

    # 설치한 공유기가 c개를 넘는지 체크 
    if cnt >= c:
        if flag == 0:
            srt = dist + 1
        else:
            break
    else:
        end = dist - 1

print(dist)

 

dist값을 기준으로 공유기를 count 했을 때 c개의 공유기 설치가 가능하더라도
house\[i\] - h == dist 라는 기준을 만족하지 않는다면 모든 인접한 공유기 간의 거리가 dist보다 큰 값을 가지게 되므로 dist는 우리가 찾는 값이 될 수 없다.

따라서 flag 변수를 사용해서 걸러내도록 하여 srt = dist + 1를 통해 다음 이분탐색을 하도록 코드를 짰다.

하지만 틀렸다..

 

맞은 코드

import sys

input = sys.stdin.readline

n, c = map(int, input().split())
house = [int(input()) for _ in range(n)]

house.sort()

# 공유기 간 거리의 범위를 (1, house[n-1]-house[0]+1)로 설정
srt = 1
end = house[n - 1] - house[0]

# 가장 인접한 두 공유기 사이의 최대 거리에 대한 이분탐색
while srt <= end:

    # 설치할 공유기가 2개일 때는 최대값을 바로 반환
    if c == 2:
        ans = house[n - 1] - house[0]
        break

    dist = (srt + end) // 2

    cnt = 1
    h = house[0]

    # 각 공유기 간 거리가 해당거리보다 같거나 클 때 설치 가능한 공유기 count
    for i in range(1, n):
        if house[i] - h >= dist:
            h = house[i]
            cnt += 1

    # 설치한 공유기가 c개를 넘는지 체크
    if cnt >= c:
        srt = dist + 1
        ans = dist
    else:
        end = dist - 1

print(ans)

 

기존 코드에서 flag 변수를 없애고,
마지막 if문에서 바로 break를 하지 않고 ans 변수에 dist값을 저장해주었다.

 

틀린 이유

틀린 코드의 마지막 if문에서 flag가 0이고 cnt>=c를 만족했더라도
다른 조합의 집들이 선택된다면, 이 전보다 더 큰 값의 dist도 cnt>=c를 만족할 수 있으니
바로 break하는 것보다 ans에 값을 저장해주고 dist가 srt+1일 때도 cnt>=c를 만족한다면 그때의 dist를 반환해주는게 맞다는 결론을 내렸다.

회고

2년전 쯤 문제를 푼 기록이 있다. 한번에 맞췄던데 그땐 풀이를 보고 풀었을 것이다.
다시 풀려니까 꽤나 오래걸렸다. 냉면먹고 배가 너무 불러서 머리가 잘 돌아가지 않았달까..
공부할 땐 적당히 먹자.
다음 이분탐색 문제를 만나면 더 빨리 풀어줄테다!