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

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

 

코드

n = int(input())


def chk(seq):
    l = len(seq)
    for i in range(2, len(seq)//2+1):
        if seq[l-i:] == seq[l-i*2:l-i]:
            return False
    return True


def bt(seq):
    if len(seq) == n:
        print(seq)
        exit()
    for i in range(1, 4):
        if seq != '' and str(i) == seq[-1]:  # 1글자 부분 수열 확인
            continue
        if chk(seq+str(i)):  # 2글자 이상 부분 수열 확인
            bt(seq+str(i))


bt('')

 

1, 2, 3 중 하나씩 붙이며 수열을 만드는데, 붙일때마다 이번에 붙인 숫자로 인해 나쁜 수열이 되는지, 즉 인접한 부분 수열과 동일한 부분 수열을 형성하게 되는지 chk() 함수로 확인해준다. 만약 형성하지 않는다면 그 숫자를 붙이고 bt() 함수를 재귀호출하면 된다. 이런 재귀 호출은 seq의 길이가 n이 될 때까지 반복되며, 우리는 작은 수부터 붙여보기 때문에 가장 먼저 완성된 길이가 n인 수열이 길이가 n인 좋은 수열 중 가장 작은 수를 나타내는 수열이다.