[1890] 점프

😲 문제

출처
N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다.

각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두 경우만 존재한다.

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램을 작성하시오.

입력
4
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0

출력
3

❗️ 문제 재정의

이러한 문제의 유형은 보통 해당 도착지점 d[i][j]가 이전 지점들의 합(d[i-1][j] + d[i][j-1])으로 생각해왔었지만,

점프를 해서 이동해야 하기에 현재 d[i][j]가 특정 지점으로 갈 수 있느냐 없느냐가 중요한 문제인 듯 싶다.

board배열에는 움직이는 칸의 수를 받고 d배열을 통해 특정 지점으로 이동하는 경우의 수를 누적하며 더해나가면 된다.

✔ 계획 수립

1. 입력받기 행렬의 크기 n, 각 칸마다 점프해야하는 값들
2. d배열 생성 후 d[0][0]은 시작점이므로 1로 초기화
3. 각 위치 (i, j)에서 board[i][j]의 값에 따라 오른쪽 또는 아래로 이동할 수 있는 경우, 해당 위치까지의 경로 수를 누적
4. board[i][j]가 0인 경우 (더 이상 이동할 수 없는 경우)를 고려하여, 이동할 수 있는 셀에 대해서만 경로 수를 계산
5. d[n-1][n-1]에는 마지막 위치까지 도달할 수 있는 모든 경로의 수가 누적된 값 출력

👨🏻‍💻 문제 풀이

n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
d = [[0]* (n) for _ in range(n)]
d[0][0] = 1
for i in range(0, n):
    for j in range(0, n):
        if board[i][j] == 0: # 핵심
            continue
        if i+board[i][j] < n:
            d[i+board[i][j]][j] += d[i][j]
        if j+board[i][j] < n:
            d[i][j+board[i][j]] += d[i][j]
print(d[n-1][n-1])

😅 회고

움직이는 방향을 이미 정해두었기에 사실 board[i][j] == 0이라는 조건만 잘세우면 어려울게 없는 문제인 듯 하다.
나는 약 30분 걸려서 문제를 풀었다..ㅠ