[백준][Python][1890][DP]점프

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

1890번: 점프

DP 길 갯수 문제 변형이다.

입력받는 배열의 원소는 그 자리에 갔을 오른쪽이나 아래로 점프를 해야되는 칸 의 갯수이다.

 

이 문제는 다음과 같이 풀 수 있다.

1. 기본적인 길의 갯수 문제를 생각하고
2. 칸의 점프 횟수를 저장한뒤,
3. 현재 위치 + 점프 시 배열을 넘지 않을경우
4. 지금 칸까지 갈수 있는 방법의 수를 더한다.
5. 그걸 아래, 오른쪽 두 가지 길에 대해 실행한다.

 

import sys

n = int(input())
d = []

dp = [[0 for _ in range(n)] for _ in range(n)]

ret = 0
for _ in range(n):
    d.append([int(i) for i in sys.stdin.readline().split()])

dp[0][0] = 1
for i in range(n):
    for j in range(n):
        if d[i][j] ==0:
            continue
        jmp = d[i][j]
        if i+jmp <n :
            dp[i+jmp][j] +=dp[i][j] 
        if j+jmp <n:
            dp[i][j+jmp] +=dp[i][j]


print(dp[-1][-1])