[C++] 백준 25346번: 다오와 트리플 멕스 게임

문제 요약

길이 N의 배열 A와 빈 배열 B, C로 트리플 멕스 게임을 진행한다. 플레이어는 다음의 두 행동을 할 수 있다.
1. A의 subsequence의 mex를 B의 맨 뒤에 적는다.
2. B의 subarray의 mex를 C의 맨 뒤에 적는다.
이때 트리플 멕스 게임의 점수는 C의 mex이다. A에 대해 얻을 수 있는 최고 점수를 구해야 한다.
(이 문제에서 빈 배열은 subsequence와 subarray로 치지 않는다.)

접근 방법

0부터 연속해서 존재하는 수가 있다면 해당 수를 제외하면서 subsequence를 만들어 볼 수 있습니다.

예를 들어,

{0, 1, 2, 3}

과 같이 입력이 주어진다면,

{1}
{0}
{0, 1}
{0, 1, 2}
{0, 1, 2, 3}

처럼 subsequence를 만들어 볼 수 있습니다. 그러면 B는

{0, 1, 2, 3, 4}

가 됩니다. 위와 비슷한 느낌으로 subarray를 만들어서 C를 만들어 보면

{0, 1, 2, 3, 4, 5}

가 됩니다. 따라서 C의 mex값은 6이 됩니다.

결과적으로, 입력을 정렬하고 0부터 연속한 숫자들을 세어 나가다가, 만약 특정한 수가 없다면 해당 수에 2를 더한 값을 출력해주면 됩니다.

단, 예외가 조금 있습니다.

만약 0이 없는 경우에는 B에 0밖에 추가되지 않기 때문에, C에는 다시 1만 추가됩니다. 그렇기 때문에 답은 0이 됩니다.

또, 0만 존재하는 경우에는

A = {0}
B = {1}
C = {0}
mex(C) = 1

이 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;

    vector<int> v(n);
    for(auto &i : v) {
        cin >> i;
    }

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

    if(v[0] != 0) {
        cout << 0 << '\n';
        return 0;
    } else if(v.size() == 1 && v[0] == 0) {
        cout << 1 << '\n';
        return 0;
    }

    for(int i = 0; i < v.size(); i++) {
        if(i != v[i]) {
            cout << i + 2 << '\n';
            return 0;
        }
    }

    cout << v.size() + 2 << '\n';
    return 0;
}