오랜만에 백트레킹 문제를 풀어봐야곘다 생각했고, 이 문제를 선택했다. 인자로 들어오는 배열이 좋은 수열인지 확인하는 함수와 백트레킹 함수로 구현했고, 처음에는 백트레킹 함수의 재귀호출 부분에서 조건문을 달지 않고 구현했다. 그러나 이렇게 되면 재귀호출의 가짓수가 너무나 많아지기 때문에 재귀호출 조건으로 다음 들어올 수를 더한 배열이 좋은 수열인지 확인한 후에 재귀호출을 하도록 코드를 수정하였고, 문제를 해결할 수 있었다.

Code

n = int(input())
answer = []
def check_arr(arr):
    l = 1
    while l <= len(arr)//2:
        for i in range(len(arr)-2*l+1):
            if arr[i:i+l] == arr[i+l:i+2*l]:
                return False
        l += 1
    return True
def find_arr(cur, arr):
    global answer
    if answer:
        return
    if cur == n:
        answer = arr
        return
    for num in ['1', '2', '3']:
        if not arr or check_arr(arr+[num]):
            find_arr(cur+1, arr+[num])
find_arr(0, [])
print(''.join(answer))