[백준 2661] 좋은수열

문제

www.acmicpc.net/problem/2661

 

알고리즘

백트래킹

 

풀이

임의의 길이의 인접한 두 개의 부분 수열이 동일하지 않도록 길이$N$까지를 결정하여 출력하는 문제입니다.

 

백트래킹 문제입니다. 처음에 빈 수열에서 시작하여 수열의 원소를 하나씩 결정해나갈때마다 '좋은수열'인지 검사합니다. 이를 통해 채워나가는 수열은 '좋은수열'로 유지할수가 있습니다. 원소가 추가된 수열에서 좋은수열인지 아닌지를 검사할 때, 추가된 원소를 포함하도록 부분 수열을 구성하기만 하면 됩니다. 예를 들어 1213에서 1을 추가하면

12131이 됩니다. 우리는 첫번째 1과 두번째 2가 좋은 수열인지 검사할 필요가 없습니다. 마지막 수열 1을 포함하는

1, 31과 인접한 수열만 검사하면 됩니다. 이렇게 길이 $N$의 수열을 구성했다면, 그 수열은 가장 작은 좋은수열임을 알 수 있습니다. 

 

나쁜수열을 만들었다면, 남은 길이를 만들어 볼 필요가 없음을 생각하며 구현하도록 합시다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;
string STR[3] = { "1", "2", "3" };
int N;
bool ok(string s) {
    int len = s.size();
    int st = len - 1;
    for (int i = 1; i <= len / 2; ++i) {
        string a = s.substr(st - i, i);
        string b = s.substr(st, i);
        if (a == b)
            return false;
        st--;
    }
    return true;
}

void solve(int len, string s) {
    if (!ok(s))
        return;
    if (len == 0) {
        cout << s;
        exit(0);
    }
    for (int i = 0; i < 3; ++i) {
        solve(len - 1, s + STR[i]);
    }
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N;
    solve(N, "");
    return 0;
}