[백준 15903번] 카드 합체 놀이 (C++)

문제링크 : https://www.acmicpc.net/problem/15903

15903번: 카드 합체 놀이

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

ll arr[1000];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    cin >> N >> M;
    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }

    ll sum = 0;
    ll result = 0;

    while(M--)
    {
        sort(arr, arr+N); //오름차순으로 정렬
        sum = arr[0] + arr[1]; //제일 작은 2개 더해주기
        arr[0] = sum;
        arr[1] = sum;
    }

    for(int i=0; i<N; i++)
    {
        result += arr[i];
    }

    cout << result;


    return 0;

}

먼저 정렬을 해주고 시작하는데 정렬을 해주고 나서 맨 앞에 제일 작은 2개의 값을 더해준다.

더해준 값을 각각 첫 번째와 두 번째 값에 할당해줘서 바꿔준다.

바꿔줌으로서 배열의 정렬순서가 바뀔 수도 있으므로 다시 정렬을 해주고 위에 작업을 다시 해준다.

 

이 작업을 M번 반복하고 나면 배열의 값 수정은 모두 끝나기에 현재 배열에 들어있는 모든 값을 더해주고 출력한다.

 

주의해야할 것이 배열의 값 범위는 1 ~ 100만이지만 M번 반복하면서 더해준 값이 들어갈 때 int 범위를 초과할 수 있기 때문에 배열 및 해당 값들이 담기는 값에는 long long으로 선언해야 한다.

 

이렇게 일일히 정렬하지 않고 우선순위 큐를 이용하여 풀수도 있다.

 

arr[0] -> pq.top() -> pq.pop()

arr[1] -> pq.top() -> pq.pop()