[Algorithm] Baekjoon 10597번 : 순열장난

https://www.acmicpc.net/problem/10597

10597번: 순열장난

map<int, int> m;
int targetCount = 0;
int isCheck = false;
string stand = "";
string result = "";
 
 
void DFS(string sum, int index, int count)
{
    if (count == targetCount)
    {
        isCheck = true;
        result = sum;
        return;
    }
 
    for (int i = 1; i <= 2; i++)
    {
        int temp = stoi(stand.substr(index, i));
 
        if (m[temp] == 0 || m[temp] == 2) continue;
 
        m[temp] = 2;
        DFS(sum + stand.substr(index, i) + " ", index + i, count + 1);
        m[temp] = 1; // 되돌려 놓기.
 
        if (isCheck) return;
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> stand;
 
    if (stand.size() <= 9)
    {
        for (int i = 0; i < stand.size(); i++)
        {
            cout << stand[i] << ' ';
        }
 
        return 0;
    }
 
    int maxNum = 9 + (stand.size() - 9) / 2;
    targetCount = maxNum;
 
    for (int i = 1; i <= maxNum; i++)
    {
        m[i] = 1; // 범위 내의 숫자지만 아직 탐색안한 숫자.
    }
 
    DFS("", 0, 0);
 
    cout << result << endl;
}

 

1부터 N까지의 숫자가 공백없이 주어졌을 때, 어떻게든 순서를 찾아서 한칸씩 띄우고 출력해야한다.

일단 N까지 한개씩의 숫자가 사용되기 때문에 그점을 이용해서 targetCount와 사용여부를 체크할 map을 선언하고 값을 채웠다.

맵에 값을 채울 때 각 값은 3가지의 상태를 지닌다.

0은 아예 범위밖의 값이고 (N이 15까지인데 그 이상의 값을 참조하려 할 경우),

1은 범위내의 값이며 아직 탐색안한 값

2는 범위내의 값인데 이미 탐색을 한 값이다.

 

주어진 문자열을 1개나 2개씩 체크하다 보면 N은 15여도 2개짜리를 체크할때 41을 체크하는 경우가 있기 때문이다.

그렇기 때문에 상태를 3가지로 나눠서 검사해봤다.

 

그 외에는 평범한 백트래킹문제다.