좋은수열

코드

#include <iostream> 
#include <algorithm> 
#include <vector> 
#include <deque>
#include <map>
#include <cmath>
#include <numeric>
using namespace std;
int N;
bool check(string str)
{
    int MAX = str.length()/2;
    for(int size=1;size<=MAX;size++)
    {
        for(int i=0;i+size+size<=str.length();i++)
        {
            string fix = str.substr(i,size);
            string cmp = str.substr(i+size,size);
            if(fix == cmp) return false;
        }
    }
    return true;
}
void DFS(int depth, string str){
    if(depth == N){
        cout << str;
        /* exit으로 바로 프로그램 종료해주는 것이 핵심! */
        exit(0);
    }else{
        for(int i=1;i<=3;i++)
        {
            if(!str.empty() and str.back() -'0' == i) continue;
            if(!check(str+to_string(i))) continue;
            DFS(depth+1, str+to_string(i));
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    DFS(0,"");
    return 0;
}

• key point
  • 가장 먼저 나오는 수가 제일 작은수이기 때문에 바로 exit(0)으로 종료해주는 것

• 느낀점
  • 조건을 걸었기 때문에 O(3^N)까지는 아니더라도 시간이 많이 나올것같아서 백트래킹을 못하지 않을까 했으나 exit(0) 덕분에 해결
  • exit(0)으로 프로그램을 바로 종료하는 좋은 것을 깨달음!