백준 2661 좋은 수열

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

백트래킹 문제입니다. 숫자가 작기 때문에 나이브하게 짜도 금방 결과가 나옵니다.

#include <bits/stdc++.h>
using namespace std;
string ans;
int n;
bool myf(string x){
    int sz=x.size();
    for(int i=2;i<=sz/2;i++){
        if(x.substr(sz-2*i,i).compare(x.substr(sz-i,i))==0) return true;
    }
    return false;
}
bool dfs(int b, int x){
    if(x==n){
        cout<<ans<<'\n';
        exit(0);
    }
    for(int i=1;i<=3;i++){
        if(i==b) continue;
        ans+=('0'+i);
        if(myf(ans) || !dfs(i,x+1)) ans.pop_back();
    }
    return false;
}
int main(void){
    cin>>n;
    dfs(0,0);
    return 0;
}