[BOJ 2661] 좋은수열

문제 출처 : https://www.acmicpc.net/problem/2661

 

풀이 :

 

백트래킹 문제입니다.

1,2,3 중 하나의 수로 들어가는데 들어가기전에 맨 뒤에서 부터 한개씩 두개씩 ~ 확장하면서 같은 부분 수열이 있는지 유망성 검사를 해주고 들어가시면 됩니다.

 

#include<stdio.h>
 
int n,arr[81],type;
 
bool backtracking(int itr)
{
    if (itr > n)return true;
    for (int i = 1; i < 4; i++) {
        arr[itr] = i;
        for (int j = 1; 2 * j <= itr; j++) {
            type = 0;
            for (int k = 0; k < j; k++) {
                int c = itr;
                if (arr[c - k] != arr[c - j - k])break;
                if (k == j - 1)type = 1;
            }
            if (type)break;
        }
        if (type)continue;
        if(backtracking(itr + 1))return true;
    }
    return false;
}
 
int main() {
    scanf("%d", &n);
    backtracking(1);
    for (int i = 1; i <= n; i++)printf("%d", arr[i]);
}