2661 - 좋은수열

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

처음에는 Naive한 코드를 만들었다. N<20 정도에 대해서 출력을 살펴보기로 한 것이다. 출력이 아래와 같았다. (출력 자체만으로 힌트는 충분했다.)

1
12
121
1213
12131
121312
1213121
12131231
121312313
1213123132
12131231321
121312313212
1213123132123
12131231321231
121312313212312
1213123132123121
12131231321231213
121312313212312131
1213123132123121312

앞의 수열이 계속 유지되면서 위에 1/2/3 중에 하나가 계속 붙는다. (자세히보면 N=7 과 N=8 인 수열은 조금 다르다.)

이전의 수열($a_k$)에 1/2/3 중에 하나를 붙여서 "인접한 두 개의 부분 수열이 동일한 것이 있는 지"를 확인하고, 없다면 조금 더 이전($a_{k-2}$)부터 다시 만들어보면 된다.
이렇게 하면 k-2 부터 다시 재귀를 하는건데, (1/2/3을 선택)^3 = 9번만 해보면 되니까 얼마 안걸린다. (이전의 수열은 유지된다)

#include <cstdio>
#include <cstring>

int n;
char trace[81];

inline bool almost(char *s){
    int i, k, len = strlen(s);
    for(k=0; k<len; ++k){
        for(i=1; i<=len/2; ++i){
            if(k+i >= len) break;
            if(strncmp(s+k, s+k+i, i)==0) return false;
        }
    }
    return true;
}

bool f(int pos){
    if(pos == n){
        if(almost(trace)){
            // puts(trace);
            return true;
        }
        return false;
    }
    for(int i=0; i<3; ++i){
        trace[pos] = i+'1';
        if( f(pos+1) ) return true;
    }
    return false;
}

int main(){
    char ret[81][85]={};
    for(n=1; n<81; ++n){
        bool find = false;
        for(int i=0; i<3; ++i){
            trace[n-1] = '1'+i;
            if(trace[n-2] == trace[n-1]) continue;
            if(almost(trace)){
                find = true;
                break;
            }
        }
        if(!find) f(n-3);
        strcpy(ret[n], trace);
        // puts(ret[n]);
    }
    scanf("%d", &n);
    puts(ret[n]);
    return 0;
}