백준 #2661 좋은수열

코드

import sys
sys.stdin = open("input.txt")

def solve(cur):
    if cur == n:
        print("".join(result))
        exit()
        return

    for i in range(1, 4):
        if cur == 0:
            result.append(str(i))
            solve(cur + 1)
            result.pop()
        else:
            result.append(str(i))
            for j in range(2, cur + 2, 2):  # 2칸씩 늘리면서 진행
                temp = result[cur - j + 1:] 
                k = j // 2
                if temp[0:k] == temp[k:]:
                    result.pop()
                    break
            else:
                solve(cur + 1)
                result.pop()


n = int(input())
result = []
solve(0)

풀이

백트래킹의 늪에 빠져버렸다.. 오늘 푼 문제는 슬라이싱 처리만 좀 헷갈리고 무난했던 것 같다.

가장 최근의 수를 포함해서 배열 길이를 2, 4, … 짝수개로 늘려가며 반을 잘라 좌, 우를 확인했다.

맞힌 사람들의 풀이를 봤는데 따로 특이한 풀이는 보이지 않았다!

화이팅팅!!