반응형
1715번: 카드 정렬하기
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장
www.acmicpc.net
코드
import heapq
import sys
n = int(input())
h = []
for _ in range(n):
num = int(sys.stdin.readline())
heapq.heappush(h,num)
if n == 1:
print(0)
exit()
answer = 0
while len(h)>1:
a = heapq.heappop(h)
b = heapq.heappop(h)
sum = a+b
answer+=sum
heapq.heappush(h,sum)
print(answer)
설명
전에 올린 파일합치기3 문제와 동일하다. 힙을 이용해서 작은 수 두 개를 뽑아서 더해준 뒤 다시 힙에 넣어주면 된다.
2022.05.03 - [알고리즘/그리디] - [백준][Python] 13975번 파일 합치기 3
[백준][Python] 13975번 파일 합치기 3
13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개
imzzan.tistory.com
대신 이 문제에서는 주어진 묶음이 하나이면 비교할 묶음이 없기 때문에 0을 출력해줘야 한다.
반응형
'알고리즘 > 그리디' 카테고리의 다른 글
| [백준][Python] 11256번 사탕 (1) | 2022.09.20 |
|---|---|
| [백준][Python] 1439번 뒤집기 (0) | 2022.05.25 |
| [백준][Python] 13975번 파일 합치기 3 (0) | 2022.05.03 |
| [백준][Python] 2812번 크게 만들기 (0) | 2022.05.02 |
| [백준][Python] 2141번 우체국 (0) | 2022.04.29 |
댓글