백준) 1715 카드정렬하기 - python, 힙 정렬

💭 나의 접근 방법

---

두 묶음의 합이 작은것 끼리의 합이니까 작은것부터 차례대로 합을 구하려고 접근하였다. 

but, 앞에서 부터 합이 뒤에 묶음보다 큰 경우 중복 덧셈을 하기 때문에 수가 커질수 있는 문제를 간과하였다.

반례)

4

20

30

40

45

-> 20+30 이 다음수 40보다 크기 때문에 50 + (50 + 40)을 하면 50이 중복 덧셈이 되기 때문에 안됨!

 

따라서, heappop, heappop 한 두개의 작은 값을 다시 힙 정렬에 넣어 작은수를 꺼낼수 있도록 구현해야한다.

 

 

 

💡 결과코드

---

import heapq
import sys
input = sys.stdin.readline

N = int(input())
q = []
answer = 0

for _ in range(N):
    heapq.heappush(q,int(input()))
if len(q) == 1:
    print(0)
else:
    while len(q) > 1:
        a = heapq.heappop(q)
        b = heapq.heappop(q)
        answer += (a+b)
        heapq.heappush(q,a+b)
    print(answer)

⚠️ len(q) == 1 인경우는, 카드 묶음이 하나인 경우인데 이때는 카드 비교를 하지 않기때문에 0이다. 

 

 

💫 느낀점

---

 문제의 다른 경우의 수를 간과하게 되면 접근 방향이 완전히 달라지기때문에 문제를 꼼꼼히 읽고, 접근방법을 고민하는 시간을 더 늘려야한다.

 

 

 

 

1715번: 카드 정렬하기