문제

링크

풀이

DFS를 이용한 백트래킹으로 문제를 풀었다. 깊이는 n까지 탐색한다. (코드에서는 배열 인덱스 편의성때문에 1부터 시작하여 n+1까지 탐색한다. 깊이는 n으로 같다.) 랭퍼드 수열을 저장하는 explore 배열에서 x와 y의 인덱스에 위치한 원소는 y - x - 1이다. x와 y사이에 거리가 x, y의 인덱스의 위치한 원소와 같다는 사실을 문제에서 알 수 있기 때문에 랭퍼드 수열을 미리 만들어놓고 시작한다.

depth 사이에는 정확히 depth 개의 수가 있다는 점을 주목하자. 랭퍼드 수열을 만들 때 한 번에 두 개의 숫자를 배치하면서 DFS를 진행한다. DFS를 진행할 때 depth가 y - x - 1일 때는 과정을 건너뛰어야 한다. 위에서 랭퍼드 수열을 미리 만들어놨기 때문에 탐색할 필요가 없다. 위 조건이 없을 경우에 랭퍼드 수열에 중복된 숫자가 들어가 오답을 만들게 된다. 수학문제처럼 노트에 쓰면서 일정한 규칙을 발견했고, 이를 DFS로 풀었다.

코드

# PyPy3만 통과 / Python3 시간초과
import sys

input = sys.stdin.readline
n, x, y = map(int, input().split())
ans = 0
explore = [0] * (2 * n + 1)
explore[x] = explore[y] = y - x - 1


def dfs(depth):
    global ans
    if depth == (y - x - 1):
        dfs(depth + 1)

    if depth == n + 1:
        ans += 1
        # print(explore)
        return

    for i in range(1, len(explore) - depth - 1):
        if explore[i] == 0 and explore[i + depth + 1] == 0:
            explore[i] = explore[i + depth + 1] = depth
            dfs(depth + 1)
            explore[i] = explore[i + depth + 1] = 0


dfs(1)
print(ans)