[알고리즘] 백준 - 좋은 수열

백준 - 좋은 수열

내 풀이

import sys

sys.setrecursionlimit(10**7)

N = int(input())

def back_tracking(cur_path, max_length):
    if len(cur_path) == max_length:
        print(cur_path)
        exit()

    for i in range(1, 3+1):
        tmp = cur_path + str(i)
        for k in range(len(tmp)-1):
            tmp2 = tmp[k:]
            if tmp2[: len(tmp2)//2] == tmp2[len(tmp2)//2:]:
                break
        else:
            back_tracking(tmp, max_length)

back_tracking("", N)

최대 길이가 80이여서 충분히 백트랙킹으로 풀 수 있고, 매번 새로운 깊이로 들어갈때 탐색을 하고 들어갈 수 있다. 탐색하는 방법은 완전 탐색으로 반복되는 구간이 있는가 없는가 검색하는 것이다.