[C++][백준 15703] 주사위 쌓기

문제

접근 방법

주사위가 올려진 상황에서 남은 주사위 중 가장 낮은 수의 사용할 수 있는 주사위를 사용하는 것이 이득일 것이다. (큰 수는 사용할 수 있는 범위가 넓으므로 그렇다)

한차례 주사위를 쌓으면 남은 주사위가 있을 것이다.
동일하게 낮은 수의 주사위를 위주로 사용하여 쌓으면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> v;
int N, answer, nCount;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> N;

    v = vector<int>(N);

    for (int &i : v)
    {
        cin >> i;
    }

    sort(v.begin(), v.end());

    for (int i = 1; i <= N; ++i)
    {
        int count = 0;

        for (int j = 0; j < N; ++j)
        {
            if (count <= v[j])
            {
                ++count;
                ++nCount;

                v[j] = -1;
            }
        }

        if (nCount == N)
        {
            cout << i;
            break;
        }
    }
    return 0;
}

풀이

우선순위 큐로 먼저 푼 뒤 정렬을 사용했다.

우선순위 큐로 풀 때는 pair을 활용하여 걸러진 횟수와 주사위의 수를 묶어서 낮은 순으로 두었다. 그렇게 하면 걸러진 횟수가 낮을수록 앞서기에 이전에 부적합하면서 주사위의 수가 낮은 경우는 후순위로 갔다.
하지만 우선순위 큐는 삽입, 제거 시 O(logN)정렬이 이루어지기에 한번 정렬하고 탐색하는 것보다 비 효율적이었다.

정렬로 푸는 방법은 정렬 이후 동일하게 사용할 수 있으면서 주사위의 수가 낮은 주사위부터 사용한다. 사용한 값은 배제하는 표시를 하여 다시 사용할 수 없게 해주었다.