BOJ 26215 - 눈 치우기 (Python)

S3, 구현, 우선순위 큐

풀이

최대 힙을 통해 우선순위 큐를 구현해 해결

• 가장 큰 값, 두번째 값을 힙에서 추출해
  • 1, 2, 5의 경우, 5, 2
• 두 값의 차이 만큼 cnt에 더해주고, 해당 차이 값을 다시 힙에 push
• 원소가 하나 남을 때 까지 반복
  • 원소가 하나 남았다면 해당 원소 값 만큼 cnt에 +

from sys import stdin
import heapq
n = int(stdin.readline())
snows = list(map(int, stdin.readline().split()))
cnt = 0
heap = []
for snow in snows:
    if snow > 1440:
        print(-1)
        exit(0)
    else:
        heapq.heappush(heap, -snow)

while len(heap) > 1:
    max_val = -heapq.heappop(heap)
    sec_val = -heapq.heappop(heap) if heap else 0

    heapq.heappush(heap, -(max_val - sec_val))
    cnt += sec_val

cnt += -heapq.heappop(heap) if heap else 0
print(-1 if cnt > 1440 else cnt)