[Algo] 백준 1890_점프

백준 1890_점프

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

import sys;sys.stdin=open("input.txt")

N = int(input())
G = [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 dp[r][c] and G[r][c] and r + G[r][c] < N:
            dp[r + G[r][c]][c] += dp[r][c]
        if dp[r][c] and G[r][c] and c + G[r][c] < N:
            dp[r][c + G[r][c]] += dp[r][c]
print(dp[N-1][N-1])

• 시작점이 0,0이고, 도착지가N-1, N-1 로 정해져있다.
• 시작점에서 갈 수 있는 경로에만 DP 테이블을 채워주면 된다.
• 그래서 dp[r][c]에 값이 존재 할 때만 테이블을 작성해준다.

💯 DP 문제의 경우 무조건 일정한 규칙을 가지고 dp테이블에 값을 채워준다. 명심