[baekjoon] 백준 15903번(파이썬): 카드 합체 놀이

문제

15903번: 카드 합체 놀이

- 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이이다!

- 아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다.

- 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다.

- 카드 합체는 다음과 같은 과정으로 이루어진다.

1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.

- 이 카드 합체를 총 m번 하면 놀이가 끝난다.

- m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다.

- 이 점수를 가장 작게 만드는 것이 놀이의 목표이다.

- 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다.

- 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, a2, …, an이 공백으로 구분되어 주어진다. (1 ≤ ai ≤ 1,000,000)

알고리즘

- 카드의 개수와 카드 합체를 몇 번 하는지 입력받는다.

- 카드의 상태를 나타내는 자연수를 입력받는다.

- 카드의 상태를 나타내는 자연수를 힙 푸시하여 리스트에 넣는다.

- m번 반복하여 카드를 합친다.

- 제일 작은 두 카드를 팝하여 더하고 더한 값을 다시 푸시하여 리스트에 넣는다.

- 리스트에 합을 출력한다. 

코드

import sys
import heapq

n, m = map(int, sys.stdin.readline().split())
card = list(map(int, sys.stdin.readline().split()))
res = []

# 카드를 힙푸시하여 리스트에 넣는다.
[heapq.heappush(res, i) for i in card]

# m번 반복하여 카드 합체 놀이를 한다.
for i in range(m):

    # 카드 리스트에서 제일 작은 두 카드를 팝한다.
    x = heapq.heappop(res)
    y = heapq.heappop(res)
    
    # 제일 작은 두 카드를 더한다.
    total = x + y
    
    # 합친 카드를 다시 푸시하여 리스트에 넣는다.
    heapq.heappush(res, total)
    heapq.heappush(res, total)

# 리스트에 합을 출력한다.
print(sum(res))

github

junjange/CodingTest