좋은수열 (feat. 백준, 2661번)

좋은수열
https://www.acmicpc.net/problem/2661

2661번: 좋은수열

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string>
using namespace std;
int N;
void solution(string str){
    register int i = 0;
    while(++i <= str.size() / 2){
        string t1 = str.substr(str.size() - i, i);
        string t2 = str.substr(str.size() - i * 2, i);
        if(!t1.compare(t2))
            return;
    }
    if(str.size() == N){
        cout << str;
        exit(0);
    }
    else{
        solution(str + "1");
        solution(str + "2");
        solution(str + "3");
    }
}
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    cin >> N;
    solution("");
    return 0;
}
// *&)*@*

 

 

1. 문자열에 "1"을 추가하고 성공한다면 다시 "1"부터 추가하는 백트래킹 방식입니다.
2. 예를 들면 "12"에 "1"을 추가한다면 12|1 와 같이 앞 2와 뒤 1은 다르므로 성공이고 1|21 은 앞 1보다 뒤 21의 길이가 더 크므로 비교대상이 아닙니다. (추가 가능)
3. 또한 "121"에 "2"를 추가한다면 121|2 와 같이 앞 1과 뒤 2는 다르므로 성공이고 12|12 는 앞 12와 뒤 12가 서로 같으므로 실패입니다. (추가 실패)
   따라서 다음 "3"이 "121"에 추가될 수 있습니다.