[BOJ] 1436 - 영화감독 숌 (c++)

소요 시간 1시간

난이도 별하나

 

규칙을 찾기 보다 dfs로 만들고, 중복제거하고, 정렬(nlogn)하는 것이 맞는듯.

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

char arr[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
string new_arr = "";
set<int> answer;

void dfs(int length)
{
    if (new_arr.size() == length)
    {
        // 666이 가장 앞에 삽입될 경우
        string s;
        s = "666" + new_arr;
        answer.insert(stoi(s));

        // 666이 중간에 삽입될 경우
        for (int i = 1; i < length; i++)
        {
            s = new_arr.substr(0, i) + "666" + new_arr.substr(i, length);
            if (s[0] == '0')
                continue;
            answer.insert(stoi(s));
        }

        // 666이 가장 뒤에 삽입될 경우
        if (new_arr[0] != '0')
        {
            s = new_arr + "666";
            answer.insert(stoi(s));
        }

        return;
    }

    for (int i = 0; i < 10; i++)
    {
        new_arr.push_back(arr[i]);
        dfs(length);
        new_arr.pop_back();
    }
}

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

    int N;
    scanf("%d", &N);

    answer.insert(666);
    int length = 1;
    while (1)
    {
        dfs(length);
        if (answer.size() >= N)
        {
            break;
        }
        length++;
    }

    vector<int> v;
    v.assign(answer.begin(), answer.end()); // 중복제거 중요 예) Dfs에서 66이 만들어졌을경우 앞 가운데 뒤 666을 삽입한 값은 모두 같다.
    sort(v.begin(), v.end());
    cout << v[N - 1];
}