[백준 알고리즘] 1715번 : 카드 정렬하기 (Python) 문제 풀이

문제

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

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 최소 비교 횟수를 출력한다.

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

1715번: 카드 정렬하기

 

문제 풀이 : 

이 문제를 풀때 처음에는 간단하다고 생각했다. 하지만, 언제나 그렇듯. 이것을 코드로 구현하는 것은 어렵다.... 

문제의 예시처럼 10, 20, 40 카드가 주어졌을때,

그에 대한 최소 비교값은 100이다.

최소?? 최적해?? 욕심?? -> 그리디 알고리즘이다. ㅋ

 

우선은 그리디 알고림을 써야한다는 것은 알겠다. 

그렇다면 식은 어떤식으로 구현을 해야할까? 

우선은 문제에 써있듯 정렬은 되어있다. 

그렇다면 우리가 해야하는 것은 어떠한 구조를 써서, 이것을 잘 빼서 더하느냐

 

예시를 참고해 보자

어떠한 구조가 있다고 가정하고, 그 구조는 10,20,40이 들어있다. 

10 과 20를 빼내어 더한다. -> 30을 다시 어떠한 변수에 넣는다. ->

30를 다시 집어넣는다. -> 30, 40 ->

다시 30과 40을 더한다. -> 70을 다시 30에 넣었던 변수와 더해준다.

-> 여기서 나는 우선순위 큐를 생각했다.

우선순위 큐란, 데이터를 추가한 순서대로 제거하는 선입선출(FIFO) 특성을 가진 일반적인 큐의 자료구조와 달리, 데이터 추가는 어떤 순서로 해도 상관이 없지만, 제거될 때는 가장 작은 값을 제거하는 독특한 특성을 지닌 자료구조이다.

 

아래는 내 코드이다.

from queue import PriorityQueue
 
que = PriorityQueue()
 
num = int(input())
for i in range(num) :
    card = int(input())
    que.put(card)
 
answer = 0
 
while(que.qsize() != 1):
    num1 = que.get()
    num2 = que.get()
    sum = num1 + num2
    answer += sum
    que.put(sum)
 
 
print(answer)

https://github.com/ois0886/BJ_Python/blob/main/BJ_1715.py

GitHub - ois0886/BJ_Python