2661. 좋은수열

https://boj.kr/2661

문제의 조건

신경 써야할 부분은 아래의 세 조건이다.

• 길이가 $N$인 수열 중 가장 작은 수열이어야 한다. $(N \leq 80)$
• 좋은 수열이어야 한다.

단순하게 계산하기

완전탐색으로 모든 경우의 수를 확인하면 계산량이 어떻게 되나 알아보자.

모든 경우의 수 (Brute Force)

각 자리에는 1, 2, 3 중 하나만 올 수 있으므로, 길이가 $N$ 인 수열이 만들어지는 모든 경우의 수는 $3^{N}$이다.

이 때의 계산량 $T(N)$ 을 구해보면:

최악의 경우에는 $1.4780883e+38$ 의 계산량을 갖게 된다.

연속하는 수를 배제

연속하는 수가 있으면 반드시 나쁜수열이므로, 연속하는 수가 나오는 경우를 배제해보자. 이때 나올 수 있는 경우의 수는 $3 \times 2^{N-1}$이다. 이 때의 계산량 $T(N)$ 을 구해보면:

목표 계산량 $1e+8$ 에 비해, 단순한 완전탐색으로는 도저히 풀 수 없어보인다. … 그럼 어떻게 풀어야 할까?

가장 작은 좋은 수열

문제에서 요구하는 정답은 가장 작은 좋은 수열이다. 즉, 수열을 오름차순으로 만들어나간다면 가장 먼저 나타나는 좋은 수열이 정답이 된다.

가능한 모든 수열을 오름차순으로 얻는 방법

완전탐색의 일종인 백트레킹으로 만들어 나갈 수 있을 것 같다.

아래와 같이 수열을 이룰 수 있는 숫자를 차례로 방문하면서 수열을 조합해나가는 것이다.

좋은 수열인지 검사하는 방법

수열 $a$ 에서 임의의 부분 수열 $(a_{s}, a_{s+1}, …, a_{e-1})$ 에 대하여, 다음을 만족하면 이를 좋은 부분 수열이라고 하자.

임의의 수열 $a$ 가 좋은 수열인지를 검사하려면, 해당 수열에서 모든 짝수 길이의 부분 수열이 좋은 부분 수열인지 검사하면 된다.

예를 들어,

• 다음은 부분 수열 $(1,2,1,2)$ 가 좋은 부분 수열이 아니므로, 좋은 수열이 아니다.

• 다음은 부분 수열 $(1,2,1,3,1,2,1,3)$ 이 좋은 부분 수열이 아니므로, 좋은 수열이 아니다.

• 다음은 부분 수열 $(2,2)$ 가 좋은 부분 수열이 아니므로, 좋은 수열이 아니다.

• 다음은 모든 부분 수열이 좋은 부분 수열이므로 좋은 수열이다.

이 때의 계산량 $T(N)$ 을 구해보면 다음과 같다: ($2^{k}$는 부분수열의 크기이다.)

시간 복잡도

추산해보면 백트래킹 기법으로 길이가 $N$인 수열 $a$ 를 생성하는데에는 $O(2^N)$의 시간이 필요하고, $a$ 가 좋은 수열인지 검사하는데에는 $O(NlogN)$의 시간이 걸린다.

종합해보면 이 문제는 $O(2^{N}NlogN)$ 의 시간 복잡도를 가진다고 볼 수 있다.

최적화

다음은 $N = 8$ 일 때, 좋은 수열을 찾아 나가는 과정이다.

아래로의 진행은 새로운 원소의 생성을 의미하고, 위로의 진행은 기존 원소의 제거를 의미한다. 붉은 색 노드는 해당 지점에서 좋은 수열이 아님을 의미한다.

여기서, 좋은 수열인지 검사를 하게 되는 시점을 보면 아래와 같다.

위 그림들을 통해 알 수 있는 것이 있다.

• 임의의 지점에서 좋은 수열이 아님을 알게되는 순간, 해당 지점에서 더 탐색해 나아갈 필요가 없다.
• 임의의 부분 수열에서 변화가 없다면, 해당 부분 수열은 다시 검사하지 않아도 괜찮다.
  → 즉, 가장 마지막으로 갱신된 원소를 포함한 부분 수열만 좋은 부분 수열인지 검사하면 된다.

하지만, 여전히 이론상 최악의 시간복잡도는 $O(2^N N \log{N})$ 이긴 하다. 과연 이 최적화로 인해 시간이 기적적으로 단축이 될까… 걸어보는 수 밖에 없다.

…

근데 귀신같이 통과되긴 했다. 매우 안정적으로. 🫠

코드 (Python3)

import sys
from typing import List


def sample_in():
    import io
    sys.stdin = io.TextIOWrapper(io.BytesIO())
    sys.stdin.write('\n'.join([
        '80',
    ]))
    sys.stdin.seek(0)


def solve():
    N = int(sys.stdin.readline())
    stack = []
    backtrack(stack, N)


def backtrack(stack: List[int], sentinel: int) -> bool:
    if len(stack) == sentinel:
        print(''.join(map(str, stack)))
        return True
    for i in (1,2,3):
        stack.append(i)
        if is_good(stack):
            if backtrack(stack, sentinel):
                return True
        stack.pop()
    return False


def is_good(sequence: List[int]) -> bool:
    if len(sequence) >= 2:
        for subseq_size in range(2, len(sequence)+1, 2):
            if not is_good_sub(sequence[-subseq_size:]):
                return False
    return True


def is_good_sub(subsequence: List[int]) -> bool:
    assert len(subsequence) % 2 == 0
    mid = len(subsequence) // 2
    for i, j in zip(subsequence[:mid], subsequence[mid:]):
        if i != j:
            return True
    return False


if __name__ == '__main__':
    # sample_in()
    solve()