[백준2661번] 좋은수열 / Python3

문제

숫자 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

7

예제 출력 1

1213121

나의 풀이

해당문제는 DFS를 사용해 수열의 앞자리부터 숫자를 채워가면서 부분수열이 중복되는지를 체크해주면 되는 문제이다.

결국 이 문제에서 핵심은 DFS는 물론이고 부분수열의 중복이 있는지 확인하는 로직이었던 것 같다.

우선, 각 단계에서 수열의 길이를 2로 나눈 몫만큼의 길이까지 비교해야한다는 것을 알아채야했다. 예를들어 1231231일때는 수열의 길이가 7이므로 부분수열의 길이를 3이 되는 것까지 확인을 해야한다는 것이다.

이제 각 길이마다 수열의 맨 뒤에서부터 인덱스를 알아내서 부분수열이 같은지를 확인해야한다. 인덱스를 구하는 수식을 구해보면 아래와 같다.

// 현재 수열의 길이 : l
// 부분 수열의 길이 : j
seq[l-(2*j):l-(2*j)+j], seq[l-(2*j)+j:]

코드

# 2661번 좋은수열

def dfs(l, seq):
    for j in range(1, l//2+1):
        if seq[l-(2*j):l-(2*j)+j] == seq[l-(2*j)+j:]:
            return

    if l == n:
        print(*seq, sep='')
        exit(0)

    for i in range(1, 4):
        if seq and seq[-1] == i:
            continue
        dfs(l+1, seq+[i])

n = int(input())
dfs(0, [])