[알고리즘/그리디] 15903번 : 카드 합체 놀이 - python

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

 

 

---

• 문제
• 소요시간: 7분 42초

---

• 설계하기(접근방법) 

1. 입력받기

입력받을 카드의 개수가 최대 100만개이다. 시간복잡도를 고려해야한다

 

2. 구현하기

카드의 합을 가장 작게 만드는 법은, 가장 작은 카드끼리 더해서 새로운 합을 만드는 것이다

누적합의 개념을 생각하면 쉽게 이해할 수 있을 것이다

 

해당 개념을 사용하려면 리스트의 최소 원소 2개를 추출할 수 있어야한다.

일반 리스트로는 100만개의 원소를 다 처리할 수 없다

 

따라서 heapq를 import하여 항상 최소 원소를 빠르게 뱉어낼 수 있도록 선언하자

 

합체 횟수만큼, heappop을 2번하여 더한 후, 그 결과를 heappush하면 된다

 

3. 출력하기

heap의 sum을 출력해준다

 

---

• 코드(출력)

import heapq

n, m = map(int, input().split())

temp = list(map(int, input().split()))

card_list = []

for i in temp:
    heapq.heappush(card_list, i)

while m:
    small_1 = heapq.heappop(card_list)
    small_2 = heapq.heappop(card_list)
    total = small_1 + small_2
    
    heapq.heappush(card_list, total)
    heapq.heappush(card_list, total)
    
    m -= 1

print(sum(card_list))

---

• 얻어갈 부분

1. 그리디와 heapq가 섞인 문제였지만 체감 난이도는 실버 3이었던것 같다