BOJ백준 1890 점프 풀이(Python)

문제는 위와 같으며 전형적인 DP(Dynamic Programming)문제이다.

DP의 의의는 이전에 계산했던 값들을 이번에 구할 값을 계산할 때 응용함에 있으므로 이를 중심으로 생각해보자.

예를 들어 A와 B라는 칸에서 C로 갈 수 있다고 해보자. 그렇다면 칸C까지 갈 수 있는 경우의 수는 칸A와 칸B까지 갈 수 있는 경우의 수의 합이 될 것이다.

이를 이용하며 시작점부터 차례대로 게임판을 순회하며 각 칸에서 갈 수 있는 칸에 현재 칸까지 오는 경우의 수를 더해준다.

아래는 소스코드이다.

import sys
N = int(sys.stdin.readline())
board = []
for i in range(N):
    temp = list(map(int, sys.stdin.readline().split()))
    board.append(temp)
 
dp = []
for i in range(N):
    dp.append([])
    for j in range(N):
        dp[i].append(0)
 
dp[0][0] = 1
for i in range(N):
    for j in range(N):
        if i==N-1 and j==N-1:
            break
        value = board[i][j]
        down = i + value
        right = j + value
 
        if down < N:
            dp[down][j] += dp[i][j]
        if right < N:
            dp[i][right] += dp[i][j]
 
print(dp[N-1][N-1])
 
# 해결

개선할 점, 비판 및 지적은 언제나 환영입니다.