1. 좋은 수열

2. 알고리즘 접근

좋은 수열 문제는 DFS 문제다.
처음에는 접근 방법을 (알고리즘)을 떠올리지 못했다.
N<=80이면 충분히 dfs를 떠올릴 법도 했는데 알고리즘 분류를 봤다.
좋은 수열 문제는 백트래킹 알고리즘을 이용해야 한다.

3. 구현

구현에 큰 문제 중 하나는 좋은 수열 판별 법이었다.
문자열 검색 알고리즘(KMP 등)을 사용하기에 문제가 너무 무거워 보였다.
그런데 백트래킹을 생각해보면, 가지치기로 복잡도를 낮출 수 있었다.

예를 들어 다음과 같은 수열을 예시로 보자.

121231

1212까지 검색한 문자열에 대하여 뒤의 문자들을 더 검색할 이유가 없다.
왜냐하면 1212로 부터 시작하면서 바로 나쁜수열이 되기 때문이다.
이러한 경우, 바로 탐색을 종료하면 된다.

그렇다면 어떻게 좋은 수열을 판별할 까?
나는 다음과 같은 방법을 이용했다.

0. 만약 검사해야할 문자의 개수보다, 문자열/2의 크기가 크다면 중단.
1. 맨 뒷자리부터 문자 N개씩 검사(총 2번 검사)
2. 만약, 두 수열이 같다면 `거짓` 반환
3. 아니라면 N++; 
4-1. 0으로 돌아가기
5. 중단 됐다면 (모든 경우의 수 탐색 했다면) `참` 반환

bool checker(string &arr)
{
    int cnt = 1;
    while (true)
    {
        if (cnt > arr.size() / 2)
            return true;
        string s1 = "";
        string s2 = "";
        // [마지막 문자 - N: 맨 마지막 수열]
        for (int i = 0; i < cnt; i++)
        {
            s1 += arr[(arr.size() - cnt) + i];
        }
        // [마지막 문자 - 2*N: 마지막 문자 - N]
        for (int i = 0; i < cnt; i++)
        {
            s2 += arr[(arr.size() - cnt * 2) + i];
        }
        if (s1.compare(s2) == 0)
        {
            return false;
        }
        cnt++;
    }
}

dfs는 딱히 추가 할 설명이 없다.
단, 초기조건으로 answer변수가 한번이라도 대입되면 값을 출력하고 종료하는 조건을 넣었다. (아니라면, 맨 마지막 좋은 수열이 출력될 것이므로)

앞서 말한 것 처럼 백트래킹을 이용하기에 checker 함수에서 거짓이 반환되면 바로 종료하는 모습이다.

아래는 소스코드 원본이다.

// https://www.acmicpc.net/problem/2661
// 2022-09-11 17:01:03

#include <bits/stdc++.h>
using namespace std;

int N;
vector<char> arr;
string answer = "";

bool checker(string &arr)
{
    int cnt = 1;
    while (true)
    {
        if (cnt > arr.size() / 2)
            return true;
        string s1 = "";
        string s2 = "";
        for (int i = 0; i < cnt; i++)
        {
            s1 += arr[(arr.size() - cnt) + i];
        }
        for (int i = 0; i < cnt; i++)
        {
            s2 += arr[(arr.size() - cnt * 2) + i];
        }
        if (s1.compare(s2) == 0)
        {
            return false;
        }
        cnt++;
    }
}

void dfs(string str)
{
    if (answer.compare("") != 0)
        return;
    if (!checker(str))
        return;
    else if (str.size() == N)
    {
        answer = str;
        return;
    }

    dfs(str + "1");
    dfs(str + "2");
    dfs(str + "3");
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N;
    dfs(answer);
    cout << answer;
    return 0;
}