https://www.acmicpc.net/problem/1715
1715번: 카드 정렬하기
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장
www.acmicpc.net
문제
풀이
우선순위 큐를 활용하여 문제를 구해주면 됩니다. 문제의 예시를 통해 직접 구해보면 알다시피 다음과 같은 로직이 성립하게 됩니다.
1. 큐 안에서 가장 작은 수 2개를 꺼내서 더해준다.
2. 더한 값을 총합(변수:ans)에 더해준다.
3. 더한 값을 다시 큐에 넣어준다.
4. 1-3과정을 큐 안에 원소가 2개 이상일 때까지 반복해준다.
코드
# 1715번 카드 정렬하기
from heapq import heappop, heappush
import sys
queue = []
n = int(input())
for _ in range(n):
heappush(queue, int(sys.stdin.readline()))
ans = 0
while len(queue) > 1:
minimum_first = heappop(queue)
minimum_second = heappop(queue)
new_num = minimum_first + minimum_second
ans += new_num
heappush(queue, new_num)
print(ans)
출력결과
'백준 > 스택 & 큐' 카테고리의 다른 글
[백준][Python] 10799번 쇠막대기 - 실버 2 (0) | 2024.03.13 |
---|---|
[백준][Python] 28278번 스택 2 - 실버 4 (0) | 2024.03.12 |
[백준][Python] 3986번 좋은 단어 - 실버 4 (0) | 2024.03.11 |
[백준][Python] 5397번 키로거 - 실버 2 (0) | 2024.03.10 |