[BOJ][python] 1890. 점프

https://www.acmicpc.net/problem/1890

1890번: 점프

---

💡IDEA

동적계획법을 사용하는 문제이다.

현재 위치에 적혀있는 값만큼 오른쪽 또는 아래쪽으로 점프해서 이동하여 도착지점(0)에 다다르는 경로의 개수를 구해야 한다. 처음에는 BFS 문제인 줄 알았으나 DP로 풀 수 있는 문제였다.

시작점을 1로 두고 모든 행렬을 돌면서 점프한 후의 위치에 이전 DP값을 끌고가면 된다. 거치지 않는 부분은 0이므로 아무것도 더해지지 않고 계속 0이고, 점프해서 갈 수 있는 길이 있다면 점프하기 이전 값을 사용한다.

마지막 도착지점(0)은 모든 경로에서 하나씩 다다르게 되므로 누적합을 더해 출력해준다.

 

📌CODE

import sys
input = sys.stdin.readline

N = int(input())
maps = [list(map(int, input().split())) for _ in range(N)]

dp = [[0]*N for _ in range(N)]
dp[0][0] = 1
for r in range(N):
    for c in range(N):
        if r == N-1 and c == N-1 :
            print(dp[r][c])
            break
        for dr, dc in [(0, 1), (1, 0)]:
            nr = r + dr*maps[r][c]
            nc = c + dc*maps[r][c]
            if 0<=nr<N and 0<=nc<N:
                dp[nr][nc] += dp[r][c]