[Python] BOJ(백준) 1715번 - 카드 정렬하기

링크

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

난이도(solved.ac 참고)

골드4

풀이

우선 예제에 대한 해석이 필요하다. 10 20 40 이라면 10 + 20을 하는 과정에서 횟수가 30만큼 증가되고, 이후에 30 + 40을 하는 과정에서 30에 70을 더해서 값이 100이 된다.

 

여기서는 heapq 모듈을 사용해서 a의 값을 줄이는 과정을 반복하고 있으므로 결국 리스트 a의 길이가 1이 되는 순간에 끝이 나야 한다. 근데 그 값은 최소가 되어야 한다. 이 경우라면 그냥 단순하게 작은 수들부터 비교를 한 뒤에 점차 큰 수와 그 비교값을 다시 비교하는 과정을 반복한다면 되겠다는 생각이 들었다.

 

그래서 최소힙이 가정되어있는 heapq에서 두 개의 값을 빼낸 다음(이 두개는 당연히 힙 내부에서 최소값일 것이다) 그 두개를 더한 값을 다시 heapq에 넣었다. 그리고 이 과정에서 진행되는 카드 정렬 횟수를 result라는 변수에 추가하였다.

 

예제를 보면서 설명을 해보면, 우선 10과 20을 큐에서 뺀 뒤에 그 두개를 더한 값인 30을 다시 큐에 넣는다. 그리고 result에는 10 + 20의 과정에서 발생한 30번의 정렬 횟수를 추가한다. 이제 큐에는 (30, 40)이 남아있다. 그 다음 이 30과 40을 큐에서 뺀 뒤에 그 두개를 더한 값인 70을 다시 큐에 넣는다. 그리고 기존 result 값인 30에 70을 더해서 100을 만든다. 이제 a의 원소의 개수는 1이 되었으므로 while문을 마친다.

 

이런 방식으로 해결하면 된다. 생각보다 어렵지 않았다. heapq 모듈을 써야 된다는 것만 생각한다면 충분히 쉬운 문제라고 생각했다.