백준 - 1715 (python)

알고리즘 스터디용 연습문제로 풀기로 한 1715번 생각보다 고생해서 적어볼까 함....ㅎ

1. 순서대로 더한다고 그게 최적은 아니다.

우선순위 힙을 이용해서 풀었다.
입력값이10, 20, 30, 40, 50 이 있다고 할때
맨 처음에 확인 할 카드 덱을 10, 20으로 잡고 계산하면 10 + 20 = 30이 된다.
이 때, 30을 힙에 push하고, 10,20을 pop했다.
그러면, 이제 힙에 30, 30, 40, 50 이 남는다.
30 + 30 = 60 이되고,60, 40, 50 이 남았다고 생각하면,
이후 60 + 40 을 하는 것보다 40 + 50 을 하는 것이 더 적은 수의 확인을 거치는 것이다.
따라서, 순서를 변경해서 40, 50, 60 순으로 계산해야만 최적이 된다.

2. input이 1개라면 비교할 필요가 없다.

이 부분에서 정말 생각보다 많은 트라이를 했는데.... 처음에는 1개의 수가 들어오면 그대로 프린트를 해주면 된다고 생각했다.
그러나 나의 큰 오산이었고..ㅜ
예를 들어 input값이

1 
10 

이 들어왔다면, 비교할 필요가 없으니까 프린트 되는 수는 10이 아니라 0이다.....그렇다....

정리

메모리도 제한이 없고, 바로 전에 최소힙, 최대힙에 대해서 공부해서 이렇게까지 어려워할 줄 몰랐는데 역시 사람은 방심을 하면 안된다쿠ㅠ....

c.f.
우선순위 힙은 트리를 배열화 하는 부분과
우선순위 힙에 insert, delete, sort하는 부분, 마지막으로 최소힙과 최대힙정도에 대해서만 알면 될 것 같다.