백준 1890번 점프 | python | dp

문제

링크

풀이

언뜻 보면 그래프 알고리즘같이 생겼으나, 모든 경로의 개수를 체크하는 것이므로 중복되는 부분 문제가 생긴다. 따라서 해당 문제는 dp로 풀이하면 된다.

먼저 dp 테이블은 게임판 크기만큼 n*n 크기의 이차원 배열로 만들어준다.
가장 오른쪽 위는 dp[0][0]=1로 초기화해준다.

게임판을 왼쪽 위부터 오른쪽 아래로 순서대로 돌면서 dp를 업데이트를 해준다.
현재 좌표를 기준으로 게임판에 적힌 값만큼 오른쪽 또는 아래로 이동했을 때의 좌표를 구하고, 해당 좌표에 현재 좌표의 dp값을 더해주면 된다. 이는 현재 위치까지 올 수 있는 경우의 수를 누적해서 담는 행위라고 생각하면 된다.

전체 코드는 아래와 같다.

import sys

input = sys.stdin.readline
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * n for _ in range(n)]
dp[0][0] = 1  # 초기 값

# 반복문을 통해 갈 수 있는 그래프의 좌표를 탐색
for i in range(n):
    for j in range(n):
        # 현재 탐색하는 좌표가 오른쪽 맨 끝 점이면 반복을 멈춘다.
        if i == n - 1 and j == n - 1:
            break

        # 오른쪽으로 이동
        if j + graph[i][j] < n:  # 범위 확인
            dp[i][j + graph[i][j]] += dp[i][j]

        # 아래로 이동
        if i + graph[i][j] < n:
            dp[i + graph[i][j]][j] += dp[i][j]

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