백준 1890 점프

문제 바로가기 -> https://www.acmicpc.net/problem/1890

✏ 생각하기

문제에서 구하는 것은 규칙을 따르며 이동할 때 [n-1][n-1]에 도달하는 경로의 개수다.
특정 지점에 도달하기 전 도착했던 지점들이 존재하고, 그 지점들에 대해서도 이전 지점들이 존재한다.
각 경로에서 선택된 지점들은 다른 영향을 받지 않고 독립적으로 선택되었다. 따라서 이 문제에서 구성되는 경로들은 모두 독립적 경로다. 따라서 다음과 같이 생각할 수 있다.

특정 지점에 도달할 수 있는 경로의 수 = sum(이전 지점에 도달할 수 있는 경로의 수)

위의 연산을 출발 지점부터 도착 지점까지 수행하면 도착 지점에 도달할 수 있는 경로의 개수를 얻을 수 있을 것이다.
한편, 문제에서 이동 규칙을 다음과 같이 규정하고 있다.

1. 반드시 오른쪽이나 아래쪽으로만 이동할 것
2. 항상 현재 칸에 적혀있는 수만큼 이동할 것
3. 이동 중 방향을 바꾸지 말 것

1번 규칙으로부터 왼쪽위에서부터 차례대로 연산을 수행하면 중복적인 계산 없이 모든 경우의 수를 고려할 수 있을 것이다.
2번 규칙으로부터 이동거리는 현재 칸에 적힌 값board[i][j]에 의해 결정되므로, 현재 칸을 이전 지점으로 두고 다음 도달 지점에 대해 연산을 수행해야 할 것이다.

📒 알고리즘

위 모든 규칙을 고려하여 다음과 같은 DP 식을 세울 수 있다.

dp[i][j] = board[i][j]에 도달할 수 있는 경로의 수
dp[i+move][j] += dp[i][j]
dp[i][j+move] += dp[i][j]

⚠ 목적지에선 위 연산이 수행되지 않도록 처리해준다.

💻 코드

import sys

n = int(sys.stdin.readline())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dp = [[0]*n for _ in range(n)]
dp[0][0] = 1  # start point
for i in range(n): 
    for j in range(n): 
        move = board[i][j]
        if move:  # if move == 0, destination
            if i + move < n: 
                dp[i+move][j] += dp[i][j]
            if j + move < n: 
                dp[i][j+move] += dp[i][j]
print(dp[n-1][n-1])