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

2661번: 좋은수열

백트래킹 연습하기 #2

 

res : 지금까지 만들어진 수열

 

is_bad() 함수의 나쁜 수열 찾는 방법

 

ex1) res = 32121

start	lo	hi
0	32	121
1	21	21

-> start=1 일 때 lo == hi 이므로 나쁜 수열이 되어 return false

 

ex2) res = 3212323

start	lo	hi
0	321	2323
1	212	323
2	12	323
3	23	23

-> start=3 일 때 lo==hi 이므로 나쁜 수열이 되어 return false

 

위의 예시를 통해 알 수 있듯이 start변수는 res 수열의 시작 인덱스를 뜻함

 

#include <bits/stdc++.h>
 
using namespace std;
 
int N;
string res = "", num = "123";
 
bool is_bad(){
    int mid = res.size()/2;
     
    for(int start = 0; start < res.size(); start++){
        int lolen = (res.size() - start)/2;
        string lo = res.substr(start, lolen);
        string hi = res.substr(start + lolen, res.size() - (start+lolen));
        if(lo == hi) return true;
    }
    return false;
}
 
void dfs(int pos){
    // 매번 실행 할 때마다 지금까지 만들어진 수열이 좋은 수열인지 확인
    if(is_bad()) return;
    
    // 좋은 수열 테스트를 통과하고 + N개의 수로 이루어 졌으면 출력하고 exit 종료
    // 가장 먼저 나온 좋은 수열이 가장 작은 좋은 수열인게 자명하다
    if(pos == N){
        cout << res;
        exit(0);
    }
    
    for(int i = 0; i < 3; i++){
        res += num[i];
//        cout << "now : " << res << endl;
        dfs(pos+1);
        res.erase(pos);
    }
    
}
 
int main(){
    cin >> N;
    dfs(0);
    
    return 0;
}