BOJ 2661 - 좋은 수열

www.acmicpc.net/problem/2661

2661번: 좋은수열

 

백트래킹을 이용해야 하는 문제다.

N 자리 수 중에서 숫자를 1, 2, 3 만을 이용하여 인접한 부분수열 중 동일한 부분수열이 나오지 않도록 해야한다

그리고 좋은 수열 중에서 작은 수를 골라야 한다.

 

작은 수를 찾아내야 되기 때문에, 문자열 앞에서 부터 시작하는게 아니라, 뒤에서 부터 시작하는게 좋다

앞자리 수가 작은 숫자일 수록 전체적으로 작은 수가 되기 때문이다.

 

 

 

- C++

#include <iostream>
#include <string>
 
using namespace std;
 
int N;
string str;
bool flag; // 좋은수열을 찾은 경우 
 
void recursion(string temp, int depth) {
    if (flag) return;
    
    int len = temp.size();
    for (int idx = 1; idx <= (len / 2); ++idx) {
        if (temp.substr(len - idx, idx) == temp.substr(len - (2 * idx), idx)) { // 뒤에서 부터 확인 
            temp = "";
            return;
        }
    }
    
    if (depth > N) return;
    
    if (depth == N) {
        flag = true;
        cout << temp;
        return;
    } else {
        for (int i = 0; i < N; ++i) {
            recursion(temp + "1", depth + 1);
            recursion(temp + "2", depth + 1);
            recursion(temp + "3", depth + 1);
        }
    }
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N;
    
    recursion(str, 0);
    
    return 0;
}