[Python] 1715번 카드 정렬하기

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

처음에 단순하게 sorted를 하고 앞에서부터 계산하면 된다고 생각해서 바로 틀렸다,,,

그리디 알고리즘 + 자료구조 문제였다.

import heapq

#1.입력
N=int(input())
cards=[int(input()) for _ in range(N)]
#2.동작 알고리즘
#앞에서부터 차례로 합침
heapq.heapify(cards)
ans=0
while len(cards)!=1:
    A=heapq.heappop(cards)
    B=heapq.heappop(cards)
    ans+=A+B
    heapq.heappush(cards,A+B)
print(ans)

https://www.acmicpc.net/board/view/142974

반례를 정리해주신 분 덕분에 다시 쉽게 알고리즘을 생각할 수 있었다,,,

 

처음에 틀리게 짰던 코드는 아래와 같다.

#1.입력
N=int(input())
cards=sorted([int(input()) for _ in range(N)])
#2.동작 알고리즘
#어차피 작은거부터 합쳐야 제일 작으니까 sorted를 함
#앞에서부터 차례로 합침
ans=0
for i in range(N):
    if i<2:
        ans+=cards[i]
    else: 
        ans+=ans+cards[i]
print(ans)

이런 쓰레기 코드를  생각하고 맞다고 생각한 나,,, 반성하자,,,,,

그리고 앞으로 반례를 생각하는 힘을 길러야겠다.

진짜 나,,,,,,