[백준] 2661번 : 좋은 수열 - Python(파이썬)

문제

www.acmicpc.net/problem/2661

2661번: 좋은수열

풀이

• 백트래킹 + BFS
• 가장 작은 수를 나타내는 수열 : 1,2,3 순으로 비교 진행
• 부분 수열 check 범위 : 전체 수열 길이의 절반

코드

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


def back_tracking(idx): 
    for i in range(1, (idx//2) + 1): 
        if s[-i:] == s[-2*i:-i]: #나쁜 순열인 경우
            return -1 
    if idx == n: #백트래킹의 깊이 = n 
        for i in range(n): #출력
            print(s[i], end = '') 
        return 0 
    for i in range(1, 4): #후보가 되는 문자열 만들기
        s.append(i) 
        if back_tracking(idx + 1) == 0: 
            return 0 
        s.pop() 

n = int(input()) 
s = [] 
back_tracking(0)