[백트래킹]2661번 좋은수열

URL : https://www.acmicpc.net/problem/2661

백트래킹 문제 어떻게 풀지?

1. 1,2,3 을 더해가며 좋은 수열인지 아닌지 판별한다고 했을 때 - dfs와 백트래킹 문제 직감

2. 종료 조건 - 좋은 순열 찾았을 때, 나쁜 순열일 경우, 길이가 n일 경우 출력

참고

c++에서 s.substr(a, b) 는 s문자열을 시작점 a에서부터 b개의 문자를 자르는 것

※필요 역량 정리하기!!!※

1. dfs + 백트래킹

2. #include<string>에서 사용하는 함수 정리하기

/*
2661 좋은 수열

백트래킹 문제

*/
 
#include<iostream>
#include<algorithm>
#include<string>
 
using namespace std;
 
int n;
bool finish;
 
bool check(string s) {
    int len = s.length();
    int start = len - 1;
    for (int i = 1; i <= len / 2; i++) {
        string first = s.substr(start - i, i);
        string second = s.substr(start, i);
        if (first.compare(second) == 0) return false;
        start--;
    }
    return true;
}
 
void dfs(int len ,string s) {
    if (finish) return;
    if (!check(s)) return;
    if (len == n) {
        finish = true;
        cout << s << endl;
        return;
    }
    dfs(len + 1, s + "1");
    dfs(len + 1, s + "2");
    dfs(len + 1, s + "3");
}
 
int main() {
    cin >> n;
    dfs(1,"1");
    return 0;
}