[백준OJ] 10597번 순열장난

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

10597번: 순열장난

---

 

-풀이-

먼저, 최대값인 N을 구해줄 필요가 있다.

공백이 사라진 순열의 길이가 10미만이라면, 이 순열은 1자리로만 이루어진 순열이 된다. 따라서 N의 값은 순열의 길이가 된다.

 

공백이 사라진 순열의 길이가 10 이상이라면, 1자리 숫자의 개수 9개와, 2자리 숫자의 개수를 더해주어야 한다. 순열의 길이를 Len이라고 할 때, N의 값은 1자리 숫자의 개수( 9 )+2자리 숫자의 개수( ( Len - 9 ) / 2 ) 가 된다.

 

N값을 구해줬다면, dfs를 이용해주어 해당 인덱스를 기준으로 한자리수와 두자리수에 대해 dfs를 실행시켜주면된다.

 

-코드-

#include <algorithm>
#include<iostream>
#include<string>
using namespace std;

string str;
int len;
int max_N;
bool visited[51]={0};
vector<int> result;

bool dfs(int index){
    if(index==len){
        for(int i=0;i<result.size();i++){
            cout<<result[i]<<" ";
        }
        cout<<"\n";
        return true;   
    }
    
    string temp="";
    int single_digit,double_digit;
    temp+=str[index];
    single_digit=stoi(temp);

    if(single_digit<=max_N&&!visited[single_digit]){
        result.push_back(single_digit);
        visited[single_digit]=true;
        if(dfs(index+1)) return true;
        visited[single_digit]=false;
        result.pop_back();
    }
    
    temp+=str[index+1];
    double_digit=stoi(temp);
    if(double_digit<=max_N&&!visited[double_digit]){
        result.push_back(double_digit);
        visited[double_digit]=true;
        if(dfs(index+2)) return true;
        visited[double_digit]=false;
        result.pop_back();
    }
    return false;
}

int main(){
    cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    
    cin>>str;
    len=str.size();
    
    if(len<10){
        max_N=len;
    }
    else{
        max_N=(len-9)/2 + 9;
    }
    
    dfs(0);
}