[힙] 백준 #15903 카드 합체 놀이 - Python

🗂️ 문제

링크: https://www.acmicpc.net/problem/15903

 

 

💡 접근법

m번의 합체 이후에 카드의 합이 가장 작은 경우를 찾아야 한다.

카드 합체의 경우 두 카드의 합을 다시 두 카드에 덮어씌우는 방식이므로, n장의 카드 중 가장 작은 두 값의 합을 덮어씌워야 최종적으로 모든 카드의 합이 가장 작아질 수 있다.

 

따라서 항상 제일 작은 두 값을 뽑아야 한다.

이때 정렬을 이용할 수도 있겠지만, 제일 작은 값이 필요하므로 최소 힙을 통해 가장 작은 값을 두 번 꺼낸다.

 

또한 두 값의 합을 아까 뽑은 카드에 업데이트해주어야 하는데, 초기 입력된 카드의 인덱스가 필요하지 않으므로 꼭 뽑은 카드에 값을 업데이트할 필요 없이 힙에 새로운 값을 두 번 추가함으로써 이를 구현할 수 있다.

 

😎 내 코드

import sys
import heapq as hq

N, M = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

hq.heapify(arr)
for _ in range(M):
    x = hq.heappop(arr)
    y = hq.heappop(arr)
    hq.heappush(arr, x + y)
    hq.heappush(arr, x + y)

print(sum(arr))

 

✅ 정답 확인