10597번

10597번 - 순열 장난

백트래킹 문제.

일단 나는 주어진 입력을 토대로 1에서 몇까지 수인지 구하기 위한 N값을 구했다.

그 다음 재귀 함수를 통해서 한칸만 가던지, 두칸만 가던지를 선택하는데, 이때 N보다는 작거나 같아야 하고,

이미 구한 값이면 안되기 때문에 bool 타입의 v벡터를 이용했다.

결과 값을 구했다면, 그 값이 맞는지 확인하고, 출력하는 방식으로 문제를 풀었다.

처음에 0 값을 생각하지 않아서 자꾸 0,1,2,3.. 이런식으로 문제가 풀렸었다. 체크할 때 0 값도 체크해서 AC받았다.

<정답 코드>

#include<iostream>
#include<string>
#include<vector>
using namespace std;
string s;
int n;
int op[51];
 
void dfs(int cnt,int pos,vector<bool> &v)
{
    if(cnt>n)
    {
        return ;
    }
 
    if (cnt == n)
    {
        bool chk = true;
        for (int i = 0; i < n; i++)
        {
            if (op[i] == -1 || op[i]==0)
            {
                chk = false;
                return;
            }
        }
 
        if (chk)
        {
            for (int i = 0; i < n; i++)
            {
                cout << op[i] << " ";
            }
            cout << "\n";
            exit(0);
        }
    }
 
    string d = "";
    int dtoi;
    for (int i = pos; i <= pos + 1; i++)
    {
        d += s[i];
        dtoi = stoi(d);
        if (dtoi <= n && !v[dtoi])
        {
            op[cnt] = dtoi;
            v[dtoi] = true;
            dfs(cnt + 1, i+1, v);
            op[cnt] = -1;
            v[dtoi] = false;
        }
    }
}
 
int main()
{
    cin >> s;
    
    if (s.size() < 10)
    {
        n = s.size();
    }
    else
    {
        n = 9 + (s.size() - 9) / 2;
    }
 
    vector<bool> v(n + 1,false);
 
    dfs(0,0,v);
 
    return 0;
}