BOJ/백준-1715-python

문제📖

풀이🙏

• 정렬된 두 묶음의 숫자 카드가 있다고한다.
• 각 묶음의 카드의 수를 A, B라 하면 두 묶음을 합쳐서 하나로 만드는 데에는 A+B번의 비교를 해야한다.
• 10장, 20, 40장의 묶음이 있다고한다면
  -> (10 + 20) + (30 + 40) = 100 번의 비교 (최소 비교)
  -> (10 + 40) + (50 + 20) = 120 번의 비교 (덜 효율적인 비교)
• 첫째 줄에 N이 주어진다.
• N의 개수만큼 카드 묶음의 크기를 한 줄에 하나씩 입력받는다.
• 가장 효율적인 최소한의 비교를 출력하라.
  -> Greedy 알고리즘 문제이다.
  -> 정렬된 두 묶음의 숫자 카드가 있다고 주어지니 sort는 하지 않는다.
  -> 문제의 목표는 두 카드 묶음의 합이 최소가 되도록 만든는것이 목적이다.
  -> while True: if len < 2: break else: A+B = min(result)
  -> (최소/최대)힙 문제이다. heapq사용!
  -> list로 card를 입력받은 후, heapify로 list를 heap으로 변환
  -> 카드의 묶음수가 A+B의 비교를 해야하는 문제이므로 pop을 사용하면 묶음 수가 꺼내(요소 삭제)어지므로 list len == 1 이 될 때까지 반복하는 구조를 갖게한다.

코드💻

## boj, 1715 : 카드 정렬하기, python3
import sys
import heapq

N = int(input())
card = [int(sys.stdin.readline()) for _ in range(N)]

heapq.heapify(card)
result = 0

while len(card) is not 1:
    s = 0
    
    for i in range(2):
        s += heapq.heappop(card)
    
    result += s
    heapq.heappush(card, s)
    
print(result)

결과😎

출처📝

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

github

github