[C++/백준] 15903번: 카드 합체 놀이

문제 링크

15903번: 카드 합체 놀이

 

풀이

처음엔 백트래킹인가 했는데, 어차피 중복으로 카드를 뽑아도 되고 최소 숫자를 구하는 것이기 때문에 정렬해서 풀면 되는 것이라 판단했다. 중간에 캐싱할 때 형을 잘못 넣어서 틀렸는데 바꿔주니 바로 성공
생각해보니 우선순위 큐로 풀어도 되는 문제

1. m번 뽑을 때까지 계속해서 배열을 오름차순 정렬하고 제일 밑에 있는 두개를 뽑아 더해서 적용한다.
2. cards를 돌면서 answer 갱신 후 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int n, m;
    cin >> n >> m;
    vector<long long> cards(n);
    for (int i = 0; i < n; i++)
    {
        cin >> cards[i];
    }

    for (int i = 0; i < m; i++)
    {
        sort(cards.begin(), cards.end());
        long long x = cards[0];
        long long y = cards[1];
        cards[0] = x + y;
        cards[1] = x + y;
    }

    long long answer = 0;
    for (int i = 0; i < cards.size(); i++)
    {
        answer += cards[i];
    }

    cout << answer;
}