[백준/1715/파이썬] 카드 정렬하기

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

1715번: 카드 정렬하기

조건

• 정렬된 두 묶음의 숫자 카드가 있따.
• 각 묶음의 카드의 수를 A,B라고 하면, 보통 두 묶음을 합쳐서 하나로 만드는데 A+B 번의 비교를 해야함.
• 하지만, 고르는 순서에 따라 비교 횟수가 달라짐. 최소한의 비교 횟수를 구해라.

입력

10 , 20 , 40 100

SOL)

우선, 입력이 크기 순서대로 주어진다는 법이 없음.

(10,20,40 이든, 10 40 20 이든 ,40 10 20 이든 다 100이 나와야함)

idea1)입력받는 값을 리스트에 일단 다 넣고, sorting 해주고, 합을 계산해주면 됨.

 

idea2)입력받는값을 히프(우선순위 큐)에 넣어주고, 최소힙이니까 파이썬은, [0]부터 차례로 꺼내주면서. 합을 계싼해주면 됨.

합을 구해주는 과정

둘다 시간 복잡도는 O(NlogN)이고,합을 계산하는 과정은 3개의 원소가 히프안에 있다고 했을때,
 heap[0] + heap[1] 
 (heap[0]+heap[1])+ (heap[0] +heap[1]+heap[2]) 이런 식으로 진행된다.  
이런 합의 형태는 , cnt에 직접 쌓지말고, 더해주는 변수를 계속 쌓아가면서, 더해주면 됨!

아래와 같이 말이다.

 i=1 ,

sum = heap[0]+heap[1]

cnt = heap[0] +heap[1]

i =2 ,

sum = heap[0] + heap[1] + heap[1] +heap[2]  
(이건 , heap[0] + heap[1] + heap[2] 이런식으로,
더했던 수에 새로운 입력을 하나씩 쌓아야하는데, 2개씩 쌓여서, 중복이되버림)
=> 2개이상일땐, 위의 개념보단 stk에 넣고 다시 빼는게 편함.
인덱스로 하면 안되겠다.

흠. 그럼, 두개를 합하고, 저장했다가 , 
새로운 input이 오면, 두개의 합을 저장했던걸 다시 꺼내서 더하고
=>이거 완전 스택이잖아?
min_heap에 push해서, 써도 무방할듯. 왜냐면 최소힙이니까!

 

import heapq as hq

n= int(input())
total=0
min_heap=[]
for i in range(n):
	min_heap.append(int(input()))

heapq.heapify(min_heap)
while min_heap:
	a=min_heap.heappop()
	b=min_heap.heappop()
	heappush(min_heap,a+b)
	result+=a+b
print(ans)