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

[ 문제 ]

 

2661번: 좋은수열

 

[ 접근방법 ]

 

백트래킹으로 접근했기에 최악의 경우 O(3 ^ n)의 시간복잡도가 나올 수 있다. 그러나

 

제일 작은 수열만 찾기도 하고, 많은 경우 isGood 함수에서 가지치기되어 시간 내에 문제를 풀 수 있다.

 

좋은 수열인지 검사하는 함수( isGood )를 따로 만들어서 보기 쉽게 만들었다.

 

[ 소스코드 ]

 

#include <iostream>
#include <string>

using namespace std;

int n;
string str = "";

bool isGood(){
    for(int i = 1; i <= str.length() / 2; i++){
        string l = str.substr(str.length() - 2 * i, i);
        string r = str.substr(str.length() - i, i);
        if(l == r)return false;
    }
    return true;
}

bool f(int x){
    if(!isGood())return false;

    if(x == n){
        cout << str;
        return true;
    }

    for(int i = 1; i <= 3; i++){
        str.push_back('0' + i);
        if(f(x + 1))return true;
        str.pop_back();
    }

    return false;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    f(0);

    return 0;
}