백준 1715 파이썬 우선순위 큐

백준 1715 - 카드 정렬하기

문제

1715번: 카드 정렬하기

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장

www.acmicpc.net

from queue import PriorityQueue

N = int(input())

pq = PriorityQueue()

for _ in range(N):

card = int(input())

pq.put(card)

data1 = 0

data2 = 0

sum = 0

while pq.qsize() > 1:

data1 = pq.get()

data2 = pq.get()

temp = data1 + data2

sum += temp

pq.put(temp)

print(sum)

# 문제 분석과 풀이
# 먼저 선택된 카드 묶음이 비교횟수에 영향을 준다.
# 카드 개수 작은거 먼저 합쳐야 한다.
# 두 개 합친 것을 새로운 카드 묶음으로 다시 데이터에 넣고 정렬

# 딱 생각해보니 데이터 삽입, 삭제, 정렬을 자주 해야함
# 우선순위 큐 이용

그리디 알고리즘 정리 블로그

그리디 알고리즘과 우선순위 큐

그리디 그리디 알고리즘은 현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘이다. 그리디 알고리즘은 동적 계획법보다 구현하기 쉽고 시간 복잡도가 우수하다. 하지만 항상

mkisos.tistory.com