[백준/python] 15918 랭퍼든 수열쟁이야!!

내 풀이

def backtrack(i=1):
    global cnt
    if i == N+1:
        if all(i for i in arr):
            cnt += 1
        return

    if i == t:
        backtrack(i+1)
    else:
        for j in range(N*2):
            if arr[j]: continue
            if j+i+1 >= 2*N: continue
            if arr[j+i+1]: continue

            arr[j] = arr[j+i+1] = i
            backtrack(i+1)
            arr[j] = arr[j+i+1] = 0


N, X, Y = map(int, input().split())

arr = [0]*N*2

t = (Y-X-1)
arr[X-1] = arr[Y-1] = t

cnt = 0
backtrack()
print(cnt)

참고하여 개선한 풀이

def backtrack(idx=1):
    global cnt
    if idx == 2*N+1:
        cnt += 1
        return

    if arr[idx] !=0:
        backtrack(idx+1)
        return

    for i in range(1, N+1):
        if not visit[i] and idx+i < 2*N and not arr[idx+i+1]:
            arr[idx]=arr[idx+i+1]=i
            visit[i]=1
            backtrack(idx+1)
            arr[idx]=arr[idx+i+1]=visit[i]=0

N,X,Y = map(int,input().split())

arr = [0]*(2*N+1)
visit = [0]*(N+1)

t = Y-X-1
arr[X] = arr[Y] = t
visit[t] = 1

cnt = 0
backtrack()
print(cnt)

백트래킹

백트래킹을 통해 특정 패턴의 수열을 찾는 문제입니다.
제가 접근한 방법은 idx에 저장된 숫자를 하나씩 올려가며 arr의 각 자리를 순회하면서 그 자리가 비어있다면 넣어 모두 배치된 경우 카운트를 올리는 방식이었습니다.

이렇게 접근했을 때 5244ms 의 시간이 발생했고, 다른 풀이의 제출보다 훨씬 오래 걸리는 것 같아 어떻게 해야 더 빠르게 해결할 수 있는지 궁금하여 다른 사람들의 풀이를 찾아보았습니다.

결론적으로, 반대로 접근을 하면 훨씬 쉽게 해결되는 문제였습니다.
배열이 아닌 숫자를 순회하면서 접근하는 경우 훨씬 빠르게 답이 도출되었습니다.

별 차이도 없는 것 같은데 유의미한 결과를 만들어 내는 것이 신기했고, 이후에는 단순히 가지치기에만 더 신경을 쓰는 것이 아니라 다양한 관점에서 생각해보는 것도 필요하다고 느꼈습니다.