[백준] 1715번 - 카드 정렬하기

1차

아이디어

1) 한 묶음의 카드만 있다면 0번 비교
2) 카드 묶음을 오름차순 정렬
3) 한 묶음보다 많은 카드 묶음이 있다면, A+B 비교
-> 예시 10, 20, 30 이 있다면
=> (10+20) + (30+30) = 총 90번의 비교가 최솟값

코드

from queue import PriorityQueue

N = int(input())
que = PriorityQueue()
result = 0


for _ in range(N):
    que.put(int(input()))

if N == 1:
    result = 0
else:
    for i in range(N):
        tmp = que.get()
        print("tmp = ",tmp)
        if i == 0:
            result += tmp
        elif i == 1:
            result += tmp
            pretmpresult = result
        else:
            pretmpresult += tmp
            result += pretmpresult
print(result)

2차

아이디어

1차시도에서는 초기 두 값은 무조건 비교하고 그 이후로는 하나의 묶음을 추가할 때마다 직전에 비교 횟수를 더하는 방법을 생각했는데, 이렇게 하다보니 최솟값이 안 나올 때가 있다.

반례
10
10
10
10
10
10
10
10
10
10
10
출력값이 340이 나와야 하는데, 540이 나옴

내가 생각한 방식 (10+10) + (20+10) + (30+10) + ...
최솟값이 나오려면
(10+10) + (10+10) + (10+10) + (10+10) + (10+10) +
(20+20) + (20+20) +
(20+40) +
(60+40) = 340

코드

from queue import PriorityQueue

N = int(input())
que = PriorityQueue()
result = 0


for _ in range(N):
    que.put(int(input()))

if N == 1:
    result = 0
else:
    for i in range(N):
        tmp = que.get()
        print("tmp = ",tmp)
        if i == 0:
            result += tmp
        elif i == 1:
            result += tmp
            pretmpresult = result
        else:
            pretmpresult += tmp
            result += pretmpresult
print(result)