[BOJ] 2661 좋은 수열 바로가기
숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.
다음은 나쁜 수열의 예이다.
다음은 좋은 수열의 예이다.
길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다.
입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다.
첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.
BFS
def dfs(sequence):
if N == len(sequence):
print(sequence)
exit()
for i in range(1, 4):
if checkSymmetry(sequence+str(i)):
dfs(sequence+str(i))
sequence
)의 길이가 입력받은 숫자(N
)와 같다면 해당 수열을 출력하고 프로그램을 종료(exit()
)한다.sequence
)에 숫자 1, 2, 3
을 연결한 값을 대칭이 발생하는지 확인하는 함수인 checkSymmetry()
를 이용하여 나쁜 수열을 찾아낸다.대칭 확인
def checkSymmetry(sequence):
for i in range(1, len(sequence)//2+1):
if sequence[-2*i:-i] == sequence[-i:]:
return False
return True
sequence
)의 값에서 발생할 수 있는 모든 대칭 성분을 조사하여 대칭이 발생하는지 확인한다.False
를 반환하고 대칭이 존재하지 않는다면 True
를 반환한다.# BOJ 2661 좋은수열
# https://www.acmicpc.net/problem/2661
from sys import stdin
def dfs(sequence):
if N == len(sequence):
print(sequence)
exit()
for i in range(1, 4):
if checkSymmetry(sequence+str(i)):
dfs(sequence+str(i))
def checkSymmetry(sequence):
for i in range(1, len(sequence)//2+1):
if sequence[-2*i:-i] == sequence[-i:]:
return False
return True
N = int(stdin.readline())
dfs('1')