[백준] 파이썬 15903 : 카드 합체놀이

 

 

from heapq import *

n, m = map(int, input().split())
cards = [] # 카드를 넣어줄 힙

for num in list(map(int, input().split())): # 숫자들을 힙에 넣어줌
    heappush(cards, num)

for i in range(m): # m만큼 카드 합체하기 
    x = heappop(cards) # 1번째 작은 값
    y = heappop(cards) # 2번째 작은 값
    heappush(cards, x + y) # 기존의 카드가 빠지고 합이 추가됨 *2
    heappush(cards, x + y)
print(sum(cards)) # 카드의 총합을 출력

 

 

입력되는 카드들에 특정한 연산을 하고 만들 수 있는 가장 작은 점수를 계산해 리턴하는 문제였다. 

카드 x와 y를 더하고 그 값을 다시 x와 y에 넣어주는 것을 m번 반복한 다음 총합을 계산해야하기때문에 결과값이 가장 작으려면 x와 y가 첫번째로 작은 값과 두번째로 작은 값이 되어야만 했다. 그래서 최소 힙을 사용해야한다는걸 알게 됐다. 

숫자들을 힙에 넣어주고 m만큼 반복문을 돌린다. pop을 두번 해서 x와 y의 값을 구해주고 다시 x + y를 힙에 두번 넣어준다. 그리고 반복문이 끝나면 sum을 사용해 총합을 출력하게 한다. 어떤 자료구조를 사용해야할지 파악하고나니 쉽게 풀 수 있었던 문제였다.

 

 

 

 

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

15903번: 카드 합체 놀이