문제

숫자 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. 1,2,3 을 차례대로 쌓아 올립니다.
2. 한자리수, 두자리수, 세자리수 .. 차례대로 앞에서부터 모든 숫자들을 확인합니다.
3. 차례대로 쌓아 올리기 때문에 자리수가 N이 되면 바로 출력하고 끝나는 로직
   => 이중 for 문이 있기 때문에 시간초과를 가져왔습니다.

재풀이

어차피 앞에는 확인이 된 상태로 dfs를 순회하기 때문에 뒤에만 확인하면 됩니다. => 모든 숫자를 확인할 필요 없이 맨 뒤에서부터 한자리 두자리.. 만 확인해도 모든 수를 확인할 수 있습니다.

N = int(input())
def dfs(num):
    nums = ['1', '2', '3']
    if len(num) == N:
        print(num)
        quit()
    for i in nums:
        if len(num)>0:
            if num[-1] != i:
                if check(num+i):
                    dfs(num+i)
        else:
            dfs(num+i)
    pass

def check(num):
    last = len(num)
    for length in range(1, len(num) // 2 +1):  # 자리수
        if num[last-length:last] == num[last-length*2:last-length]:
                return False
    return True

dfs('')