Algorithm/Baekjoon

[Algorithm]Baekjoon 15903 :: 카드 합체 놀이

MaxLevel 2024. 1. 26. 02:59

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

 

15903번: 카드 합체 놀이

첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1,

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
using namespace std;
 
int n, m;
long long input;
priority_queue<long long, vector<long long>, greater<long long>> pq;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> input;
        pq.push(input);
    }
 
    while (m--)
    {
        if (pq.size() >= 2)
        {
            long long a = pq.top();
            pq.pop();
            long long b = pq.top();
            pq.pop();
 
            pq.push(a + b);
            pq.push(a + b);
        }
        else break;
    }
 
    long long answer = 0;
 
    while (!pq.empty())
    {
        answer += pq.top();
        pq.pop();
    }
 
    cout << answer;
}
 
 
 
 cs

 

임의의 카드 두개를 합치고, 합친값을 카드 두개에 덮어씌우는 것을 m번만큼 반복했을 때, 최솟값을 구하는 문제이다.

그냥 우선순위큐를 이용해서 제일 작은숫자들부터 합치면서 진행하면 되서 매우 쉬운문제다.