BOJ 2661 - 좋은수열 링크
(2023.05.16 기준 G4)

문제

숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이다. 그렇지 않으면 좋은 수열이다.
이 때, 길이 N이 주어진다면 좋은 수열인 N자리의 정수 중 가장 작은 수 출력

알고리즘

간단한 가지치기를 통한 백트래킹

풀이

N은 최대 80이므로 모든 가능한 수를 확인하면 O(3^80). 터진다. 적당한 가지치기 방법을 생각해보자.

일단 가장 작은 수를 구하는 문제이므로, 현재 진행 중인 정수가 저장되어 있는 정답보다 작아질 수 있는지 체크하자.

그리고 현재 진행 중인 정수가 좋은 수열인지 판별하자.

위 두 방법으로 가지치기를 하면서 진행하면 진행되는 정수는 생각보다 많지가 않다.

코드

• C++

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

int N;
string answer;

bool check(string n){
    // n이 현재 정답보다 작이질 가능성이 있어야 한다.
    if (answer < n) return false;

    // 동일한 인접한 두 개의 부분 수열이 없어야 한다.
    for (int i = 1, l = n.size(); i <= l / 2; i++){
        bool same = true;
        for (int j = l - i; j < l; j++)
            if (n[j] != n[j - i]){
                same = false;
                break;
            }
        if (same) return false;
    }

    return true;
}

void dfs(string n){
    // n의 길이가 N이 되었다면 answer 갱신
    if (n.size() == N){
        answer = n;
        return;
    }

    // 1부터 3까지 하나씩 붙여서 검사
    for (int i = 1; i <= 3; i++){
        n.push_back((char)(i + 48));
        if (check(n)) dfs(n);
        n.pop_back();
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++) answer.push_back('3');
    dfs("");
    cout << answer;
}

• Python

def check(n):
    # n이 현재 정답보다 작이질 가능성이 있어야 한다.
    if answer < n:
        return False

    # 동일한 인접한 두 개의 부분 수열이 없어야 한다.
    for i in range(1, len(n) // 2 + 1):
        if n[-i:] == n[-i * 2:-i]:
            return False

    return True

def dfs(n):
    # n의 길이가 N이 되었다면 answer 갱신
    if len(n) == N:
        global answer
        answer = n
        return

    # 1부터 3까지 하나씩 붙여서 검사
    for i in range(1, 4):
        m = n + str(i)
        if check(m):
            dfs(m)

N = int(input())
answer = '3' * N
dfs('')
print(answer)