https://www.acmicpc.net/problem/15903
15903번: 카드 합체 놀이
첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1,
www.acmicpc.net
문제 해결을 위한 과정
이 문제는 그리디 알고리즘으로 해결할 수 있는 문제였습니다. 먼저 문제를 잘 보시면 리스트에서 가장 작은 값 2개를 빼온 후 그 둘의 합을 구합니다. 그 후 합들을 리스트에 넣어줍니다.
문제 해결을 위한 팁
이때 가장 작은 값을 두 개 빼오는 과정은 sort()를 이용하여 구할 수도 있고 우선순위 큐를 이용할 수 있습니다. 파이썬의 우선순위 큐는 최소합으로 구현이 되어있기 때문에 단순히 우선순위 큐에서 빼내기만 하면 가장 작은 값을 빼올 수 있습니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
import heapq
n, m = map(int, input().split())
data = list(map(int, input().split()))
q = []
for i in range(n):
heapq.heappush(q, data[i])
for i in range(m):
x = heapq.heappop(q)
y = heapq.heappop(q)
heapq.heappush(q, x+y)
heapq.heappush(q, x+y)
print(sum(q))
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 2439: 별 찍기 - 2(Python) (2) | 2021.02.02 |
|---|---|
| 백준 알고리즘 2438: 별 찍기 -1 (Python) (0) | 2021.02.02 |
| 백준 알고리즘 2606: 바이러스(Python) (0) | 2021.01.25 |
| 백준 알고리즘 2667: 단지번호붙이기 (Python) (0) | 2021.01.25 |
| 백준 알고리즘 2178: 미로 탐색 (Python) (0) | 2021.01.19 |