문제

문제 링크

어떻게 접근할 것인가

  • 단순하게 생각해보았다.
  • 숫자를 하나씩 놓으면서 나쁜 수열을 만드는지를 확인해보고 나쁜 수열을 만든다면 손절하고 아니면 계속해서 다음 수를 놓아갔다.
  • 최소값이기 때문에 항상 1부터 놓아보면서 적절한 값을 만들었다.

코드

#include <cstdio>

int n, num[81];

int comp(int a, int b){
    int i = a, j = b;
    while(i < b){
        if(num[i] != num[j]) return 1;
        i++, j++;
    }
    return 0;
}

int make_num(int index){
    if(index == n) {
        for(int i = 0; i < n; i++)printf("%d", num[i]);
        printf("\n");
        return 1;
    }
    int succeed = 0, t = (index + 1) / 2;
    for(int i = 1; i < 4; i++){
        num[index] = i;
        for(int j = 1; j <= t; j++){
            if(!comp(index - j * 2 + 1, index - j + 1)){
                num[index] = 0;
                break;
            }
        }
        if(num[index]!= 0)succeed = make_num(index+1);
        if(succeed) return succeed;
    }
    return 0;
}
int main(){
    scanf("%d", &n);
    make_num(0);
}

느낀점

  • 백트래킹이라고 알고리즘에서 알려주지 않았더라도 이 문제를 수월하게 풀기는 어려웠을 것 같다.
  • 좀더 감을 키워내보자.