https://www.acmicpc.net/problem/1715
1715번: 카드 정렬하기
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 잘 못 생각하기가 쉬운 문제였던 것 같습니다. 저도 처음에 그냥 문제를 해결하려 하였다가 틀렸었고 백준 사이트에 질문게시판을 보고 접근방식이 잘못되었다는 것을 알게 된 후 해결할 수 있었던 문제였습니다.
먼저 heap을 이용해야 합니다. 파이썬의 경우 최소 힙 형태로 구현이 되어있기 때문에 보다 쉽게 해결할 수 있었습니다. 예시를 그림과 같이 보겠습니다.
(원래 heap은 트리의 형태로 구현되지만 시인성을 위해 큐의 형태로 그림을 표현하였습니다.)
1. 각 원소들을 heapq에 넣어준다.
| 10 | 20 | 40 |
2. heapq에서 원소 두개를 빼준후 더한다.
10 + 20 = 30
| 30 |
3. 합한 값을 heapq에 넣어준다
| 30 | 40 |
4. heapq에서 원소 두개를 빼준 후 더한다.
30 + 40 = 70
| None |
5. 2번에서 구한 30 과 4번에서 더한 70을 더해 100을 만든다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
import heapq
q = []
N = int(input())
for i in range(N):
heapq.heappush(q, (int(input())))
sum = 0
while len(q) > 1:
temp1 = heapq.heappop(q)
temp2 = heapq.heappop(q)
heapq.heappush(q, (temp1+temp2))
sum += temp1+temp2
print(sum)
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 2810: 컵홀더 (Python) (0) | 2021.01.19 |
|---|---|
| 백준 알고리즘 13305: 주유소(Python) (0) | 2021.01.19 |
| 백준 알고리즘 2437: 저울 (Python) (0) | 2021.01.03 |
| 백준 알고리즘 18353: 병사 배치하기(Python) (0) | 2020.12.21 |
| 백준 알고리즘 14501: 퇴사 (Python) (1) | 2020.12.19 |