[백준,c++] 17255번 - N으로 만들기

문제

17255번: N으로 만들기

 

코드

#include <iostream>
#include <map>
#include <set>
using namespace std;


string s;
map<set<string>,int> visited;
void dfs(int left, int right, string now, set<string> temp){
    if(now.length()>=s.length()){
        if(now == s) visited[temp] = 1;
        return;
    }
    if(left>0){
        temp.insert(s[left-1]+now);
        dfs(left-1, right, s[left-1]+now, temp);
        temp.erase(s[left-1]+now);
    }
    if(right<s.length()){
        temp.insert(now+s[right+1]);
        dfs(left, right+1, now+s[right+1], temp);
        temp.erase(now+s[right+1]);
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>s;
    
    for(int i=0; i<s.length(); i++){
        string temp = "";
        set<string> set_temp = {temp+s[i]};
        dfs(i,i, temp+s[i], set_temp);
    }
    cout<<visited.size();
}

 

풀이

일단 N의 최대 길이가 8밖에 되지 않기 때문에 충분히 백트랙킹을 이용해서 풀 수 있는 문제입니다.

다만 조건에서  "숫자를 적는 과정에서 나온 수가 순서대로 모두 같다면 같은 방법이다." 라고 했기 때문에 중복되는 과정은 카운팅 하지 않아야 합니다. 따라서 set에 만든 과정들을 담아서 중복 과정들을 모두 제거하는 방향으로 해결했습니다.