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

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

---

DFS로 모든 경우의 수를 체크해주면 된다.

 

1. 2N+1 길이 arr 배열을 만든다. (default = 0)
2. 해당 숫자를 사용했는지 안했는지 체크하는 N+1 길이 used 배열을 만든다.
3. X와 Y자리 숫자는 항상 같으므로 arr[X] = arr[Y] = Y-X-1 로 설정한다.
4. dfs함수를 통해 x가 2N+1이라면 수열이 완성된것이므로 count해준다.
5. arr[x]가 0이 아니라면 이미 숫자가 들어있으므로 다음칸을 계산하는 dfs(x+1)을 실행한다.
6. 숫자가 들어있지 않다면 사용하지 않은 숫자(j) 중에서 arr[x+j+1]에도 숫자가 들어있지 않다면 해당 숫자를 사용한다.

 

import sys
input = sys.stdin.readline
 
N, X, Y = map(int, input().split())
used = [False]*(N+1)
arr = [0]*(2*N+1)
used[Y-X-1] = True
arr[X] = Y-X-1
arr[Y] = Y-X-1
answer = 0
 
 
def dfs(x):
    global answer
    if x == 2*N+1:
        answer += 1
        return
    if arr[x] != 0:
        dfs(x+1)
    else:
        for j in range(1, len(used)):
            if not used[j] and x+j+1 < 2*N+1 and arr[x+j+1] == 0:
                used[j] = True
                arr[x] = j
                arr[x+j+1] = j
                dfs(x+1)
                used[j] = False
                arr[x] = 0
                arr[x+j+1] = 0
 
 
dfs(1)
print(answer)