[백준 2661번] 파이썬 - 좋은 수열

백준 2661 - 좋은 수열

시간 제한 1초, 메모리 제한 128MB

# 조건

• 숫자 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들 사이에는 빈칸을 두지 않는다.

# 접근 방법

• 전체 수열을 만들고 체크하면 시간 초과가 발생한다.
• 따라서, dfs와 백트래킹을 사용하여 풀어준다.
• 사용할 수 있는 수는 1, 2, 3이므로 순열을 만들 반복문은 range(1, 4)의 범위로 돌려준다.
  • 수열 뒤에 수를 추가해주며 나쁜 수열인 경우엔 return을 한다.
• 좋은 수열인지 나쁜 수열인지 체크하는 방법은
• 123123의 경우
  • 1자리
    • 1, 2, 3, 1, 2, 3
  • 2자리
    • 12, 31, 23
    • 23, 12와 같이 체크해야되는데
  • 3자리
    • 123 123
• 숫자를 추가하는 경우 좋은 수열인 경우만 추가하였으니 뒤의 2개만 확인해주면 된다.
  • 위의 예를 다시 보면 1 2 3 1 2 에서 뒤에 3을 추가하는 경우
  • 1자리 비교는 2 와 3만 비교
  • 2자리는 31과 23을 비교
  • 3자리인 경우 123 123을 비교
  • 즉, 1 ~ 현재 길이 // 2 + 1 범위로 비교를 하며
  • -i, -2 * i ~ -i 를 비교해주면 된다.
• 길이가 N과 같다면 좋은 수열이면서 최소를 만족한 경우이므로 바로 출력해주면 된다.

import sys  
input = sys.stdin.readline  

# idx는 현재 추가된 수의 인덱스 = 만들고 있는 수열의 현재 길이  
def good_permu(idx):  
    # 이미 앞에는 좋은 수열만 추가되었으므로  
    # 추가된 수를 포함하며 뒤에서 2개만 절반의 길이만큼만 체크해주면 된다.    
    # 즉, 123123의 경우    
    # 뒤에서 3 과 2, 31 과 23, 123 과 123을 비교해준다.    
    for i in range(1, idx//2 + 1):  
        if result[-i:] == result[-2*i:-i]:  
            return 0  

    if idx == N:  
        print(*result, sep='')  
        return 1  

    for i in range(1, 4):  
        result.append(i)  
        if good_permu(idx+1):  
            return 1  
        result.pop()  

N = int(input())  
result = []  
good_permu(0)