더블릿_좋은 수열

백트래킹 문제에 대해서 조금씩 감을 잡아가는 느낌이다.

이 문제는 완전 탐색을 하는 도중 첫 번째 답이 나오면 종료하는 것이 포인트다. 

나의 백트래킹 가지치기는 1부터 3으로 한 칸씩 늘려나가면서 만들어 가므로 

가장 먼저 나오는 첫 번째 답이 최소값이다. 그렇다면 더 이상 트래킹을 그만둬도 답을 도출해낼 수 있다. 

백트래킹에 대한 문제는 어느 정도 해소가 되었는데,

좋은 수열을 판별하는 방법이 의외로 까다로웠다.

처음에는 좋은 수를 판별하는 방법은 너무 복잡하고 까다롭고 분명 시간 소비를 많이 할 것 같아 

규칙을 찾아야 된다고 생각했는데, 그 것이 아니었다. 

좀 더 연구해보니까 분명 좋은 수열을 판별하는 것은 

인덱스 장난을 치는 부분이 조금 복잡하지만 절대 시간이 오래 걸리지는 않다는 것을 알았다. 

예를 들어 123123 이라는 수가 있으면

맨 끝의 인덱스부터 시작해서 length를 1부터 시작해서

length : 1

2-3 비교

-----------------------

length : 2

3 - 1

2 - 3

비교

-----------------------

length : 3

3 - 3 

2 - 2

1 - 1

비교 ===>(이 것은 나쁜 수열로 판별남)

-----------------------

이런식으로 판별했다. 

bool check_good(int targetidx){
    int length = 1;
    while (length <= (targetidx) / 2){
        int currentidx = targetidx - 1;
        bool flag = false;
        for (int i = currentidx; i > currentidx - length; i--){
            if (result[i] != result[i - length]){
                flag = true;
            }
        }
        if (!flag) return false;
        length++;
    }
    return true;
}

(현재의 점)을 기준으로 현재 점과 (현재의 점 - length)을 비교하는 과정을 통해

판별하는 것이다. 이 경우는 길이가 80이어도 40번만 수행 횟수는 정말 얼마 되지 않는다. 40번정도?

수를 완전탐색하면서 좋은 수열인지 판별하고 답이 나오면 최소값이므로 바로 종료하면 되는 문제였다.

<소스코드>

#include <iostream>
using namespace std;
 
int n;
int result[80];
int case_count = 0;
bool printflag = false;
 
bool check_good(int targetidx){
    int length = 1;
    while (length <= (targetidx) / 2){
        int currentidx = targetidx - 1;
        bool flag = false;
        for (int i = currentidx; i > currentidx - length; i--){
            if (result[i] != result[i - length]){
                flag = true;
            }
        }
        if (!flag) return false;
        length++;
    }
    return true;
}
 
void make_series(int idx){
    if (printflag) return;
    if (idx == 1 && result[0] != 1) return;
    if (idx == 6){
        if (result[0] != 1) return;
        if (result[1] != 2) return;
        if (result[2] != 1) return;
        if (result[3] != 3) return;
        if (result[4] != 1) return;
    }
    if (!check_good(idx)) return;
    if (idx == n && !printflag){
        for (int i = 0; i < n; i++){
            cout << result[i];
        }
        cout << endl;
        printflag = true;
    }
    if (idx == n){
        return;
    }
    for (int i = 1; i <= 3; i++){
        result[idx] = i;
        make_series(idx + 1);
    }
}
 
int main(){
    cin >> n;
    make_series(0);
    return 0;
}