[Python/파이썬] 백준 15918번 랭퍼든 수열쟁이야!!

15918번: 랭퍼든 수열쟁이야!!

 

코드

n, x, y = map(int, input().split())
location = [[] for _ in range(n+1)]
ans = 0
visited = [False]*(2*n)
visited[x-1] = True
visited[y-1] = True


def bt(num):
    global ans
    if num > n:
        ans += 1
        return
    if num == (y-x-1):
        bt(num+1)
        return
    for i in range(2*n-num-1):
        if not visited[i] and not visited[i+num+1]:
            visited[i] = True
            visited[i+num+1] = True
            bt(num+1)
            visited[i] = False
            visited[i+num+1] = False


bt(1)
print(ans)

 

2*N 크기의 배열에서 같은 숫자 사이에는 딱 그 숫자만큼의 원소들이 있어야 하는 수열이 문제에서 구해야하는 수열이다. 그리고 x, y자리에는 같은 수가 들어가도록 고정되어 있다. 그 말은 x, y번째 자리에는 (y-x-1) 숫자가 들어가야만 한다는 말이다. 이걸 생각하고 문제 풀이를 시작해야 한다.

 

해당 문제는 백트래킹 알고리즘을 이용해야 시간초과 없이 풀 수 있다. 백트래킹은 유망하지 않은 가지, 즉 더이상 진행해도 절대로 해가 나올 수 없는 쪽으로는 진행하지 않는 알고리즘이다.

 

여기서는 num이 y-x-1일 때는 이미 들어갈 자리가 정해져있기 때문에 재귀적으로 dfs(num+1)만 호출하고 그 아래의 코드는 실행하지 않아야 한다. 

num이 y-x-1이 아닌 수일 때는 남은 자리 중에 들어갈 수 있는 자리를 찾아서 넣어주고 dfs(num+1)을 재귀호출하여 진행하면 된다. 이때 들어갈 수 있는 자리인지 알려면 2*N의 배열 중 num 칸 간격으로 2칸이 아직 비어있는 경우인지 체크하면 된다.