[이분탐색] 백준 2110. 공유기 설치

문제

문제 해석

n개의 집들에, c개의 공유기를 설치하고자 한다.
한 집에 하나씩 설치하고, 가장 멀리씩 설치할 때
가장 인접한 거리로 설치된 간격을 출력하라.

주요 변수

low, high : 탐색 범위

    * high는 집의 끝과 끝에 설치했을 때가 가장 멀고, 공유기의 개수가 가장 적게 설치될 때의 간격인데
       문제 조건에서 공유기가 2개 이상 주어진다고 했기 때문에 high는 양 끝집을 설치했을 때보다 길 수 없다.
idx : 직전에 설치된 집의 좌표
mid : (띄워야 하는) 공유기의 최소 간격에 대한 변수

최종 코드

# 집 n개
# 공유기 c개
# 한 집에 하나, 가장 멀리씩 설치 max d

import sys
input = sys.stdin.readline
n,c = map(int, input().split())
house = sorted([int(input()) for _ in range(n)])

def getCnt(mid):
    cnt = 1
    idx = house[0]

    for i in house[1:]:
        if i >= idx + mid:
            idx = i
            cnt +=1
    return cnt

low = 1
high = house[-1] - house[0]
while low<=high:
    mid = (low + high)//2
    # mid : 공유기 거리의 최소 간격
    if getCnt(mid) >= c:
        answer = mid
        low = mid+1
    else:
        high = mid-1

print(answer)

Insight

그 외 try

[DP]

getCnt 함수 안에 dp로 설치된 집을 표시해서, 공유기 개수를 출력했다.

dp = [0]*(house[-1]+1)
if dp[i]==0 and (i - idx) >= mid:
    dp[i] = 1
    idx = i
    cnt +=1

답은 나오는데, 메모리 초과가 됐다. house 리스트의 개수가 1억개까지 입력될 수 있었기 때문에 1억의 길이를 가진 빈 리스트를 만들고 다시 접근해서 값을 읽어오고 하는 게 오히려 비효율적이었다. dp 사용없이 설치한 집의 idx(위치좌표)만 기억하면 됐었다.
if i >= idx + mid :
그래서 이 부분이 엄청 중요하다.

 

[탐색 범위 줄이기, min]

탐색 범위의 시작 변수인 low가 집이 가장 좁을 때를 기준으로 하고 싶었다. 그러면 탐색범위가 훨씬 줄어드니까.

short = 10**9
house = sorted([int(input()) for _ in range(n)])
tmp = house[0]
for h in house[1:]:
    short = min(short, h-tmp)
    tmp = h

    ... 중략
low = short

답은 나오나, 1부터 돌려서 이분탐색으로 바로 진행하는게 더 시간이 적게 들었다. for안에서 min함수로 비교하는 게, 이분탐색을 1회 더 하는 것보다 비효율적이었나보다.

 

위에가 거리 최소값 비교해서, 탐색범위를 가장 인접한 집의 간격으로 설정했을 때이다. low = 1 보다 오래 걸렸다.