2661번 좋은수열

 백트래킹 문제.

 

 재귀 + 조건을 통해 문제를 해결 -> 좋은수열인지 나쁜수열인지 확인하면서 숫자를 하나씩 늘려나간다.

 

 ex) N=3

       1 -> 11 -> 나쁜수열 -> 12 -> 좋은 수열 -> 121 -> 좋은수열 -> 이제 그만!

 

#include <iostream>
#include <string>
#define MAX 81
 
using namespace std;
 
int N;
string str;
char num[3]={'1','2','3'};
 
bool Check(string s, int cnt){
    for(int i=1;i<=cnt/2;i++){
        string cmp1 = s.substr(cnt-i,i);
        string cmp2 = s.substr(cnt-2*i,i);
        
        if(cmp1==cmp2){
            return false;
        }
    }
    return true;
}
 
void BackTracking(string s, int cnt){
    if(cnt==N){
        cout << s << endl;
        exit(0);
    }
    
    for(int i=0;i<3;i++){
        if(Check(s+num[i],cnt+1)){
            BackTracking(s + num[i], cnt+1);
        }
    }
}
 
int main(){
    cin >> N;
 
    for(int i=0;i<3;i++){
        BackTracking(str+num[i], 1);
    }
}