취준/백준
[백준][Python][1890][DP]점프
puff
2020. 2. 11. 19:46
문제 : https://www.acmicpc.net/problem/1890
1890번: 점프
문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로
www.acmicpc.net
DP 길 갯수 문제 변형이다.
입력받는 배열의 원소는 그 자리에 갔을 오른쪽이나 아래로 점프를 해야되는 칸 의 갯수이다.
이 문제는 다음과 같이 풀 수 있다.
- 기본적인 길의 갯수 문제를 생각하고
- 칸의 점프 횟수를 저장한뒤,
- 현재 위치 + 점프 시 배열을 넘지 않을경우
- 지금 칸까지 갈수 있는 방법의 수를 더한다.
- 그걸 아래, 오른쪽 두 가지 길에 대해 실행한다.
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])