백준 2110 [공유기 설치] 파이썬

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

 

이분탐색 꽤나 익숙해졌다고 생각했는데 쉽지 않았다...

 

# 백준 2110 공유기 설치

import sys
input=sys.stdin.readline

N,C=map(int,input().split())
wifis=[]
houses=[]
for _ in range(N):
    houses.append(int(input()))

houses.sort()

for i in range(C):
    wifis.append(houses[i])

for i in range(C,N):
    new_wifi_loc=wifis[-1]
    wifis[-1]=houses[i]
    wifi_curr=C-2
    while wifi_curr>0:
        old_wifi_loc=wifis[wifi_curr]
        old_diff=min(old_wifi_loc-wifis[wifi_curr-1],wifis[wifi_curr+1]-old_wifi_loc)
        new_diff=min(new_wifi_loc-wifis[wifi_curr-1],wifis[wifi_curr+1]-new_wifi_loc)
        if new_diff>old_diff:
            temp=wifis[wifi_curr]
            wifis[wifi_curr]=new_wifi_loc
            new_wifi_loc=temp
            wifi_curr-=1
        else:
            break
ans=1000000000

for i in range(1,C):
    ans=min(ans,(wifis[i]-wifis[i-1]))

print(ans)
# print(wifis)

하다하다 안돼서 그리디로 해결하려 하였는데, 해결불가.

 

 

GPT의 도움을 받았다..

import sys
input = sys.stdin.readline

N, C = map(int, input().split())
houses = [int(input()) for _ in range(N)]
houses.sort()

def can_install(min_dist):
    count = 1  # 첫 번째 집에 무조건 설치
    last_loc = houses[0]
    for i in range(1, N):
        if houses[i] - last_loc >= min_dist:
            count += 1
            last_loc = houses[i]
    return count >= C

# 이분 탐색
left = 1  # 최소 거리
right = houses[-1] - houses[0]  # 최대 거리
answer = 0

while left <= right:
    mid = (left + right) // 2
    if can_install(mid):
        answer = mid  # 설치 가능하면 답 갱신
        left = mid + 1
    else:
        right = mid - 1

print(answer)

집들의 위치를 이분탐색해야하여 적절한 순서로 삽입해야하나 생각했는데, 그게 아니라 거리를 이분탐색하여 가장 적절한 간격을 찾는것이었다..