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

문제

구조

처음에 잘못 생각했던 부분

최소한의 비교를 하려면, 최소 값이 최대한 많이 더해져야 한다고 생각해서 계속 앞에서 더한 sum 값을 가지고 뒤에 pop한 작은 수와 더해줘야 한다고 생각했다.

그.러.나.

내가 앞에서도 써놨듯이, 최소인 값을 최대한 더 많이 더하는 게 중요한데, 남아 있는 수들보다 sum한 값이 크면 sum한 값과 가장 작은 값을 더해주는 게 (최소이지 않은 값인 sum 값) + (가장 작은 값)이 되어져 버린다.

즉, 중요한 건 sum한 값을 계속 더해주는 게 아니라 sum한 값도 결국엔 pop을 해서 card 힙엔 없어진 값이므로 다시 card 힙에 push한 다음 (카드 두 개를 합친 것), 최솟값을 더 많이 더해줘야 하므로 card 힙에서 다시 두 개를 고르는 과정을 계속해줘야 하는 것이었다.

heappop()을 두 번 해주고 heappush()를 한 번 해주므로 카드는 겹치진 않는다!!

예를 들어,

입력값이
4
10
15
20
23
이라면,

[10, 15, 20, 23]
[20, 23, 25] 
# 여기서 원래대로 생각했던 로직이라면 25(마지막 값) + 20을 더했어야 하지만,
# 최소값을 구해야 하므로 20 + 23 카드를 먼저 합치는 게 최소이다.
# 최소인 값을 최대한 더 많이 더하는 게 중요하므로!
[25, 43]

그래서, 이 경우 원래 내가 생각했던 로직으로 하면 138이 나오지만, 실제 제대로 된 최소값은 136이 맞다.

그리고 처음엔 답을 프린트할 때 굳이 변수를 따로 두지 않고 arr 배열에 있던 값들을 모두 sum해주었으나, 제대로 된 로직으로 풀 땐 answer 변수를 따로 두고 거기에 계속 +=로 더해주는 방식을 취했다.

원래 풀이 (오답)

import sys
import heapq
N = int(sys.stdin.readline())
card = []

for i in range(N):
    num = int(sys.stdin.readline())
    heapq.heappush(card, num)
    
if N == 1:
    print(0)
elif N == 2:
    a = heapq.heappop(card)
    b = heapq.heappop(card)
    print(a+b)
else:
    cnt = 2
    arr = []
    a = heapq.heappop(card)
    b = heapq.heappop(card)
    arr.append(a + b)
    
    while cnt <= N-1:
        arr.append(arr[-1] + heapq.heappop(card))
        cnt += 1
    
    print(sum(arr))

정답 풀이

import sys
import heapq
N = int(sys.stdin.readline())
card = []

for i in range(N):
    num = int(sys.stdin.readline())
    heapq.heappush(card, num)
    
if N == 1:
    print(0) # 생각하지 못했던 부분 (카드가 한 묶음일 땐 비교할 필요가 없으므로 0)
elif N == 2:
    a = heapq.heappop(card)
    b = heapq.heappop(card)
    print(a+b)
else:
    answer = 0
    while len(card) > 1:
        print(card)
        # 최소인 값을 최대한 더 많이 더하는 게 중요
        # 입력값이 4 // 10 15 20 23 인 경우
        # [10, 15, 20, 23]
        # [20, 23, 25] <= 여기서 원래대로 생각했던 로직이라면 25(마지막 값) + 20을 더했어야 하지만, 최소값을 구해야 하므로 20 + 23 카드를 먼저 합치는 게 최소이다.
        # [25, 43]
        a = heapq.heappop(card)
        b = heapq.heappop(card)
        answer += a + b
        heapq.heappush(card, a+b)
    
    print(answer)