문제📖
풀이🙏
- 정렬된 두 묶음의 숫자 카드가 있다고한다.
- 각 묶음의 카드의 수를 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
