cho.sh

데이터를 추가해 주세요.

시간 제한1초메모리 제한1024 MB

문제

현빈이는 다이나믹 프로그래밍의 고수가 되고 싶어서 매일매일 백준에서 다이나믹 프로그래밍 문제를 푼다. 오늘도 어김없이 다이나믹 프로그래밍 문제를 찾던 현빈이는 다음과 같은 문제를 발견했다.

$N \times N$크기의 미로가 있다. 미로의 가장 왼쪽 위는 $(1, 1)$칸이고 가장 오른쪽 아래는 $(N, N)$칸이며 각 칸은 빈칸 또는 벽으로 구성된다. 시작점인 $(1, 1)$칸에서 출발해 도착점인 $(N, N)$칸에 도달하려 하는데 다음과 같은 규칙에 따라 이동하려 한다.

  1. 현재 위치가 $(r, c)$칸 일 때, $(r, c+1)$이 빈칸이라면, $(r, c+1)$칸으로 이동할 수 있다.
  2. 현재 위치가 $(r, c)$칸 일 때, $(r+1, c)$이 빈칸이라면, $(r+1, c)$칸으로 이동할 수 있다.
  3. 현재 위치가 $(r, c)$칸 일 때, $(r+1, c)$칸과 $(r+2, c)$칸이 빈칸이라면, $(r+2, c)$칸으로 한 번에 이동할 수 있다.

미로의 시작점과 도착점은 항상 빈칸임이 보장될 때 시작점에서 출발해 도착점에 도달하는 이동 방법의 개수를 $M$으로 나눈 나머지를 출력한다. 단, 시작점에서 출발해 도착점에 도달할 수 없다면 $-1$을 출력한다.

문제를 보자마자 너무 간단한 다이나믹 프로그래밍 문제라고 생각한 현빈이는 신나서 1분 만에 코드를 작성했다. 현빈이가 작성한 코드의 의사코드는 다음과 같다.

function solve(N, M, Map):
    DP = [N + 1][N + 1] # 0으로 초기화된 (N + 1) x (N + 1) 크기의 DP 배열 선언
    DP[1][1] = 1 % M # 시작점 설정

    # '.'은 빈칸 '#'은 벽
    for r from 1 to N:
        for c from 1 to N:
            if Map[r][c] is '#':
                continue

            if r + 1 <= N and Map[r + 1][c] is '.':
                DP[r + 1][c] = (DP[r + 1][c] + DP[r][c]) % M # 이동 방법 1

            if c + 1 <= N and Map[r][c + 1] is '.':
                DP[r][c + 1] = (DP[r][c + 1] + DP[r][c]) % M # 이동 방법 2

            if r + 2 <= N and (Map[r + 1][c] and Map[r + 2][c]) is '.':
                DP[r + 2][c] = (DP[r + 2][c] + DP[r][c]) % M # 이동 방법 3

    if DP[N][N] is 0:
        DP[N][N] = -1

    return DP[N][N]

현빈이는 위와 같은 코드를 제출하고 맞았습니다!! 를 받았지만, 이를 옆에서 지켜보던 민우는 도착점에 도달할 수 있으며 이동 방법의 개수가 $M$의 배수라면 $0$을 출력해야 하는데 현빈이의 코드는 $-1$을 출력한다며 틀린 코드라고 지적했다. 현빈이의 코드를 틀리게 하는 데이터를 추가해 보자.

입력

첫 번째 줄에 양의 정수 $M$이 주어진다. ($1 \le M \le 314\,159\,265$)

출력

첫 번째 줄에 미로의 크기를 나타내는 정수 $N$을 출력한다. ($2 \leq N \leq 60$)

다음 $N$개의 줄에 걸쳐 .과 #로만 이루어진 미로를 나타내는 문자열을 출력한다. $i$ 번째 줄의 $j$ 번째 문자는 $(i, j)$칸의 상태를 나타내며, .이라면 빈칸을, #이라면 벽을 의미하고, 시작점과 도착점은 항상 빈칸이어야 한다.