백준 2661번 : 좋은수열

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

bool isGoodSequence(const string& seq) {
    int len = seq.length();
    for (int i = 1; i <= len / 2; i++) {
        if (seq.substr(len - i) == seq.substr(len - 2 * i, i)) {
            return false;
        }
    }
    return true;
}

bool findGoodSequence(int N, string& seq) {
    if (seq.length() == N) {
        cout << seq << endl;
        return true;
    }

    for (char num = '1'; num <= '3'; num++) {
        seq.push_back(num);
        if (isGoodSequence(seq)) {
            if (findGoodSequence(N, seq)) {
                return true;
            }
        }
        seq.pop_back();
    }
    return false;
}

int main() {
    int N;
    cin >> N;

    string seq;
    findGoodSequence(N, seq);

    return 0;
}