[백준 2661 : C++] 좋은수열 / 백트래킹

문제

---

 

 

 

풀이

---

이 문제의 핵심은 좋은수열인지 판별하는 방법을 알아내는 것이다.

마지막 인덱스를 기준으로 길이를 1부터 시작해 (수열의 길이 / 2)까지 비교한다.

 

 

 

 

코드

---

C++ 언어를 이용하여 코드를 살펴보자.

#include <iostream>
#include <string>
using namespace std;

int N;
string s;
bool flag;

void func(string t, int depth) {
    if (flag) return;

    int len = t.size();
    for (int i = 1; i <= (len / 2); i++) {
        if (t.substr(len - i, i) == t.substr(len - (2 * i), i)) {
            t = "";
            return;
        }
    }

    if (depth > N) return;

    if (depth == N) {
        flag = true;
        cout << t << "\n";
        return;
    }
    else {
        for (int i = 0; i < N; i++) {
            func(t + "1", depth + 1);
            func(t + "2", depth + 1);
            func(t + "3", depth + 1);
        }
    }
}

int main() {
    cin >> N;

    func(s, 0);

    return 0;
}