[백준(파이썬/Python)] 1477_휴게소 세우기

 

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

1477번: 휴게소 세우기

 

우선순위 큐를 이용해 휴게소 사이 거리가 최대인 구간을 찾고, 해당 구간을 쪼개나가면서 최적해를 찾을 수 있는 문제입니다.

 

주의해야 할 부분은 해당 구간을 쪼갤 때 그 시점의 거리에서 절반씩 쪼개는게 아니라, 맨 처음 거리에서 N번 쪼개야 한다는 것입니다.

예를 들어, A와 B사이 거리가 맨 처음에 24였다면 이 구간을 3번 쪼갤 때, 24->12->6->3이 아니라 24 // 3 = 8이라는 것입니다.

 

이를 구현하기 위해서는 각 구간 사이 거리를 우선순위 큐에 집어넣을 때 구간을 나눈 횟수 k를 튜플형태로 넣어줘서 구현해야 합니다. 그 구간을 쪼개야 한다면 현재 거리에 k를 곱해서 원래 거리를 구하고, 원래 거리를 나눠주어야 하는 것이죠.

 

마지막 정답을 출력할 때는 k등분한 구간의 값이 정수라면 정확히 k등분된 것이지만, 소수점이 있다면 정확히 k등분으로 쪼개지지 못한 것이기 때문에 1을 더해주고 출력해주면 됩니다.

 

[풀이]

import heapq as hq

n, m, l = map(int, input().split())
facility = sorted(list(map(int, input().split())))

# 각 휴게소 사이의 거리를 최대힙 구조로 담는다.
# 거리를 큐에 담을 때는 등분한 횟수를 같이 입력하고, 초기값은 1이다.
distance = []
for i in range(len(facility)):
    if i == 0:  # 시작점~첫번째 휴게소 사이 거리
        hq.heappush(distance, (-facility[i],1))
    else:
        hq.heappush(distance, (-(facility[i] - facility[i-1]),1))
    if i == len(facility) - 1: # 마지막 휴게소~끝점 사이 거리
        hq.heappush(distance, (-(l-facility[-1]),1))
    
# 가장 긴 구간을 k등분해나간다.
for _ in range(m):
    longest, divided = hq.heappop(distance)
    # 등분하기 전 원래 거리값을 k등분으로 해줘야 한다.
    longest = -longest * divided
    hq.heappush(distance, ((-longest / (divided +1)), divided + 1))

answer = -hq.heappop(distance)[0]
if answer == int(answer):
    print(int(answer))
else:
    print(int(answer)+1)