BOJ - N으로 만들기 (17255)

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

17255번: N으로 만들기

 

최대 8자리 숫자가 들어옵니다.

들어오는 숫자가 작아서 완전탐색으로 충분히 가능합니다.

시간복잡도는 O(N * 2^N) 입니다.

 

완전탐색은 BFS, DFS 아무거나 사용해도 됩니다.

이 코드에서는 DFS로 풀었습니다.

 

경로가 같은 것은 같은 경우의 수로 가정하는데, 이를 걸러내는 방법이 여러가지 있지만

각 경로를 string으로 이어 붙여서 마지막에 set 자료구조를 사용해서 걸러내면 됩니다.

 

예를 들어서 123이 들어온다면,

 

1 -> 12 -> 123 경로를 이어붙이면 112123 이 되고, 이를 set에 insert 해주면 됩니다.

 

 

#include <bits/stdc++.h>
 
using namespace std;
 
int limit;
unordered_set<string> st;
string s;
 
// dfs로 완전탐색하기 위한 함수
void sol(int l, int r, string t) {     
    // l, r : 현재 이어붙여 온 문자열이 input으로 들어온 문자열에서의 범위
    // ex) input : 49583, 95가 현재 문자라면, 이는 input 인덱스 l = 1, r = 2에 해당한다.
    // 그 다음 스텝에서 할 수 있는 액션은 (l - 1)을 붙이던지, (r + 1)을 붙이던지 
    // 둘 중 하나이다.
    // 즉, 495 또는 958 이다.
 
    if (limit == t.size()) {    // 모든 경로를 이어붙였다면 끝낸다.
        st.insert(t);
        return;
    }
 
    if (l - 1 >= 0) sol(l - 1, r, t + s.substr(l - 1, length + 1));        // 범위를 반드시 체크해준 후에 이어붙인다.
    if (r + 1 < s.size()) sol(l, r + 1, t + s.substr(l, length + 1));
}
 
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
 
    cin >> s;    
    int l = s.size();
    limit = l * (l + 1) / 2;    // 각 경로를 다 이어붙였을 경우의 문자열 길이
 
    for (int i = 0; i < l; i++) {    // input으로 들어온 문자열의 모든 문자를 시작점으로 하여 탐색한다
        string tmp = "";
        tmp += s[i];
        sol(i, i, tmp);
    }
 
    cout << st.size();
}