[Python] BOJ 1890 - 점프(Jump the Board!)

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

1890번: 점프

# DP문제이다.

 

1. 우선 게임판 m을 입력받고 dp테이블도 m과 같은 크기로 선언해준다.

 

2. (0,0)부터 한 칸씩 이동하며 m[i][j]가 0이면 continue하고, 아니면 점프를 뛸 수 있는지 판단한다. (11, 13줄)

 

3. 점프를 뛸 수 있으면, 점프를 뛴 곳의 dp값의 현재 좌표의 dp값을 더해준다.

 

4. 맨 오른쪽 아래인 dp[-1][-1]을 출력한다.

 

import sys
input = sys.stdin.readline
N = int(input())
m = [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 m[i][j] == 0:
			continue
		if 0 <= j + m[i][j] < N:	
			dp[i][j + m[i][j]] += dp[i][j]
		if 0 <= i + m[i][j] < N:
			dp[i + m[i][j]][j] += dp[i][j]

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

(solved.ac 티어: 실버 2)