[정렬] 백준 1715 Gold4 카드 정렬하기

📌 링크 : https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

❗️ Issue 

1️⃣ DP로 풀었는데 왜 안되지?

반례)
4
2
2
3
3
→ 20이 나와야함

 

2️⃣ DP가 아니라 heapq를 써야하는 것은 알겠다 근데 왜 틀리지?

💡 Solution 

1️⃣ 일단 내가 잘못생각한게 있다 (((2,2)3)3) 이렇게 무조건 순서대로 더하는게 답인줄 착각했는데 그러면 안되는 이유는

(2,2) (3,3) 이렇게 하는 것이 최소 값이기 때문이다. 이때문에 dp를 사용하면 안되고  heapq를 사용할 수 밖에 없다.

heapq에서 빼고, 계산된값을 다시 넣어주면서 heapq 리스트의 개수가 1개가 될때까지 반복해주면 된다.

 

2️⃣ 틀린 이유는 .. ㅋㅋ 내가봐도 어이없는데 if에서 걸러줄때 print로 출력을 안했기때문이다....

3️⃣ 추가적으로 리스트 두개 만들지 말고 입력받을때부터 heapq에 넣자!

 

 

전체 코드

import heapq
N = int(input())
data = []
for _ in range(N):
    heapq.heappush(data, int(input()))

answer = 0
if (len(data) == 1):
    print(answer)
else:
    while (len(data) > 1):
        c_1 = heapq.heappop(data)
        c_2 = heapq.heappop(data)
        new_c = c_1 + c_2
        answer += new_c
        heapq.heappush(data, new_c)
    print(answer)