[백준] 2661번: 좋은수열 / Python / 백트래킹

좋은수열

• 문제
  숫자 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부터 문자열 길이의 절반 단위까지 범위를 늘려가면서 구간을 비교하면 된다.

def getResult(idx):
    global isExit
    if isExit: return 
    
    if idx >= n: 
        # 정답 출력
        print(''.join(result))
        # 첫번째 반환되는 수열이 가장 작으므로 종료하도록 설정
        isExit = True
        
    else:
        for i in ['1', '2', '3']:
            result[idx] = i
            # 현재 채워진 인덱스까지 좋은 수열인지 확인, 좋은 수열이면 다음 숫자 찾기
            if isGood(result[:idx + 1]): 
                getResult(idx + 1)
                

# 좋은 수열인지 판단하는 함수
def isGood(nums):
    # 1부터 수열 길이의 절반까지 범위를 늘려가면서 구간 비교
    for tkn_size in range(1, len(nums) // 2 + 1):
        if nums[-tkn_size:] == nums[-(2 * tkn_size):-tkn_size]:
            return False
    return True


n = int(input())
result = [0] * n
isExit = False
getResult(0)