[백준 2661] 좋은수열

문제

숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.

다음은 나쁜 수열의 예이다.

• 33
• 32121323
• 123123213

다음은 좋은 수열의 예이다.

• 2
• 32
• 32123
• 1232123

길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다.

 

입력

입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다.

 

출력

첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

---

접근

1, 2, 3으로 만들 수 있는 N자리의 수열을 만들어서 좋은수열인지 판단한다. 이때 좋은 수열이 아닌 조건을 만나면 더 이상 수열을 생성하지않고 이전 시점으로 돌아간다. 이를 통해 연산 수를 줄인다.

 

여기서 좋은 수열이 아닌 조건을 다음과 같이 설정한다.

인덱스 0 1 2 3 4 5이 있을 때 4와 5가 같은지 검사 -> (2, 3)과 (4, 5)가 같은지 검사 -> (0, 1, 2)와 (3, 4, 5)가 같은지 검사하도록 한다.

 

구현

- 먼저 수열을 생성하기 위해 numbers라는 리스트에 1, 2, 3을 하나씩 추가한다.

- numbers에 추가할 때 가장 마지막 숫자와 현재 넣을 숫자가 다를 때만 추가한다.

- for문을 통해 좋은 수열인지 아닌지 검사하여 아니라면 바로 리턴하여 더 이상 연산하지 않는다.

- 이제 idx가 N이라면 N자리의 수열을 모두 만든 것이기 때문에 출력한다.

def solve(numbers, idx):
    for i in range(1, idx//2+1):
        if numbers[idx-(2*i):idx-(2*i)+i] == numbers[idx-(2*i)+i:]:
            return
    if idx == N:
        print(*numbers, sep='')
        exit(0)

    for n in (1, 2, 3):
        if numbers and numbers[-1] == n:
            continue
        numbers.append(n)
        solve(numbers, idx+1)
        numbers.pop()

---

전체 코드

import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline

def solve(numbers, idx):
    for i in range(1, idx//2+1):
        if numbers[idx-(2*i):idx-(2*i)+i] == numbers[idx-(2*i)+i:]:
            return
    if idx == N:
        print(*numbers, sep='')
        exit(0)

    for n in (1, 2, 3):
        if numbers and numbers[-1] == n:
            continue
        numbers.append(n)
        solve(numbers, idx+1)
        numbers.pop()

N = int(input())
solve([], 0)