[Algorithm] 백준 BOJ 1477 휴게소 세우기 python 파이썬 이분탐색 골드 4

Private 난이도 : ♥♥♥♥♡

1477번: 휴게소 세우기

import sys
input=sys.stdin.readline
n,m,l=map(int,input().rstrip().split(' '))
rest=[l] # 맨 마지막 길이까지 고려해야 함
if n!=0: # n=0일때 입력이 개행만 들어오는 것 처리 -> 런타임에러(Value Error)의 원인
    x=list(map(int,input().rstrip().split(' ')))
    rest=rest+x
rest.sort()

low=1
high=l-1 # 맨 끝에는 휴게소를 세울 수 없음
result=0
def is_possible(mid):
    now=0
    new_rest=list() # 휴게소를 새로 짓게될 위치
    for r in rest:
        while (r-now)>mid: # 간격이 mid보다 크면
            now+=mid # 이 위치에
            new_rest.append(now) # 짓는다
        now=r # now 갱신

    if len(new_rest)>m: # 현재 mid길이가 길어서 휴게소를 덜 세움-> mid 줄이기
        return False
    return True
    
while low<=high:
    mid=(low+high)//2
    if is_possible(mid):
        high=mid-1
        result=mid
    else:
        low=mid+1
print(result)

설명

• 적절한 휴게소 사이의 거리를 mid로 잡고 이분 탐색
• mid를 기준으로 이미 세워져 있던 휴게소 사이에 휴게소를 세울 수 있으면 세우기
  -> cnt+=(r-now-1) // mid 를 더하고 리스트를 사용하지 않으면 더 쉽고 효율적인 것 같다.
• 주의할 점은 (r-now)>mid 에 등호를 빼야한다는 것 같을 때는 이미 휴게소가 세워진 곳에 또 세우는 꼴이 되기 때문

배운 점

• 런타임 에러 (ValueError)
  n=0인 경우가 문제였다.
  입력이 '0 99 100'만 들어오게 될 줄 알았는데 '0 99 100\n \n'이렇게 휴게소가 없을 땐 다음 줄에는 아예 비어있는 상태로 들어오는 것 같다. 그래서 아예 n=0일때 입력을 다르게 받아줬더니 해결했다
• 끝조건을 생각해야한다
  이미 지어져있는 휴게소의 마지막 휴게소가 한계가 아니라 도로의 길이가 한계이기 때문에 거기까지 포함해야해서 휴게소 리스트에 도로의 길이를 포함해주었다.