백준 2661번: 좋은수열 (Python)

접근

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

2661번: 좋은수열

백트래킹 문제였습니다. 문제에서 주어지는 N 길이의 좋은 수열 중 가장 작은 좋은 수열을 구하는 문제입니다.

이 수열은 숫자 1, 2, 3 으로만 이루어져 있으므로 첫번째 항부터 한개씩 채워가며 길이가 N 이 될 때까지 채워갑니다. 이때 숫자를 하나 채울때마다 지금까지의 수열이 좋은 수열인지 아닌지를 계속 체크해나가면서 진행하면 되고, 문제에서 가장 작은 좋은 수열을 구하라고 하였기 때문에 각 칸에 작은 수부터 (1부터 3 순서대로) 넣어보면서 좋은 수열의 조건을 충족하는지 확인하면서 진행하면 됩니다.

코드

N = int(input())
arr = []


def backtracking(idx):
    for i in range(1, (idx // 2) + 1):
        if arr[-i:] == arr[-2 * i : -i]:
            return -1
    if idx == N:
        for n in arr:
            print(n, end="")
        print()
        return 0

    for i in range(1, 4):
        arr.append(i)
        if backtracking(idx + 1) == 0:
            return 0
        arr.pop()


backtracking(0)

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!