BOJ_1715 카드 정렬하기

• TOC {:toc}

이 글은 백준 온라인 저지의 1715번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.04.29

import sys
from heapq import heappush, heappop

input = lambda: sys.stdin.readline().rstrip()

H = []
N = int(input())
for _ in range(N):
    heappush(H, int(input()))

s = 0
while len(H) != 1:
    c_new = heappop(H) + heappop(H)
    s += c_new
    heappush(H, c_new)

print(s)

아이디어 & 풀이

카드를 합칠 때마다 두 카드를 더한 새로운 카드가 생성되기 때문에 총 더한 값을 최소로 유지하려면 개수가 최소인 카드부터 더해가야 한다.

디버그

• 출력 초과됐다.

  • 처음에만 두 카드를 pop하고 이후에는 s += s + heappop(H)를 반복했었는데, s는 이전 두 카드의 합이 아니고 총 카운트인데 이걸 계속 더해나가서 값이 너무 커진 것 같다.

• 입력된 카드가 한 묶음 일 때는 비교를 아예 하지 않기 때문에 입력된 카드 값이 아니라 0을 출력해야 한다.

• 아래처럼 최솟값을 순차적으로 더해나가면서 계산했었는데 틀렸다.

  # 첫 번째 카드 묶음의 개수를 받는다.
  card_1 = heappop(H)
  while H:
      # 두 번째 카드 묶음의 개수를 받는다.
      card_2 = heappop(H)
      # 두 카드를 합치면서 세는 수를 s에 더한다.
      s += card_1 + card_2
      # card_1을 두 카드를 합친 카드 묶음으로 만든다.
      card_1 += card_2
  

  • 두 카드 묶음을 하나로 합친 결과는 새로운 카드 묶음으로 생각할 수 있고 이것보다 적은 카드를 갖는 카드 묶음이 존재할 수 있다.
  • 그러므로 카드 묶음을 여기에 순차적으로 더하는 게 아니라, 이 묶음은 push하고 다시 현재 묶음 중에서 카드의 수가 가장 적은 두 묶음을 더해야 한다.