백준 2661번 좋은수열 C++

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

 

백트래킹을 진행할때 1,2,3 순서대로 채워주면서 채운다음에 나쁜 수열인지 검사한다. 나쁜 수열이면 걸러주고 좋은 수열만 계속 백트래킹을 진행시키다가 n만큼 채워지면 그게 제일 작은 좋은 수열이다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

char chs[3] = { '1','2','3' };

int n;

void BT(string str) {
    int line = str.length() - 2;
    int len = 1;
    bool isGood = true;
    for (int i = line; i >= 0; i--) {
        int leftStart = i - len + 1;
        int leftEnd = i;
        int rightStart = i + 1;
        int rightEnd = i + len;
        if (leftStart < 0) break;

        string left = "";
        string right = "";

        for (int j = leftStart; j <= leftEnd; j++) {
            left += str[j];
        }
        for (int j = rightStart; j <= rightEnd; j++) {
            right += str[j];
        }

        if (left == right) {
            isGood = false;
            break;
        }

        len++;
    }
    if (!isGood) return;

    if (str.length() >= n) {
        cout << str;
        exit(0);
    }

    for (int i = 0; i < 3; i++) {
        BT(str + chs[i]);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    BT("");
}