[BOJ] 15903번 - 카드 합체 놀이

[BOJ] 15903번 - 카드 합체 놀이

 

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

15903번: 카드 합체 놀이

 

알고리즘

---

그리디로 생각하여 풀었다.

작게 만들기 위해서는 작은 두수를 뽑아내서 갱신시켜주어야 한다.

이때 시간 복잡도가 가장 낮은 Heap을 이용

 

1. heapq를 이용하여 Data 초기화

2. 요청받은 갯수만큼 heapq 갱신

3. 갯수 출력

 

코드

---

#BOJ 15903번
import heapq

n , m = map(int,input().split())
datas = list(map(int,input().split()))
q = []

[ heapq.heappush(q,data) for data in datas ]

for _ in range(m) :
    temp = heapq.heappop(q)+heapq.heappop(q)
    heapq.heappush(q,temp)
    heapq.heappush(q,temp)

print(sum(q))