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

https://www.acmicpc.net/problem/2661

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

 

관련 개념

이 문제는 백트래킹 문제로 분류되어 있다.

 

 

[Algorithm][JAVA] 백준 11651번: 좌표 정렬하기 2

 

11651번에서 백트래킹 관련 개념을 다룬 적이 있다.

 

코드

import sys

def isGoodArr(arr): #좋은 수열 판단 함수
    arr_len = len(arr)				#수열 길이
    for part_len in range(1, arr_len // 2 + 1):	#비교할 부분수열의 길이
        #부분수열 비교 시작
        for part_start in range(part_len, arr_len - part_len + 1):
            #같은 부분수열 발견하면
            if arr[part_start - part_len:part_start] == arr[part_start:part_start + part_len]:
                return False			#False 리턴
    else:					#모든 부분수열이 다르면
        return True				#True 리턴

def dfs(arr, depth): #백트래킹 함수
    if depth == N:				#원하는 길이가 되면 
        print("".join(list(map(str, arr))))	#수열 출력
        sys.exit()				#종료
    arr.append(1)				#1 추가 (아무 수나 상관 없음)
    for i in range(1, 4):			#1부터 3까지 반복
        arr.pop()
        arr.append(i)
        if isGoodArr(arr):			#해당 수열이 좋은 수열이면
            if not dfs(arr, depth + 1):		#다음 다리 수 시작
            #만약 다음 자리 수에서 1~3 모두 넣어도 좋은 수열이 없다면 현재 자리수 1 증가
                continue			
    else:
        #현재 자리 수 1~3 모두 넣어도 좋은 수열이 없는 경우
        arr.pop()				#이번 자리 수 없앰
        return False				#False 리턴


N = int(input())				#입력
dfs([1], 1)					#백트래킹 시작

 

참고

https://velog.io/@deannn/BOJ-%EB%B0%B1%EC%A4%80-2661%EB%B2%88-%EC%A2%8B%EC%9D%80-%EC%88%98%EC%97%B4-Python