1890번 파이썬

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

1890번: 점프

이 문제는 처음에 bfs로 접근할까 하다가 dp로 문제를 접근해봤다.

먼저 이 문제의 조건은 그 칸에 있는 수만큼 점프를 해야하고 점프는 오른쪽 또는 아래쪽 무조건 한방향으로만 쭈욱 점프할 수 있다.

문제 풀이는

처음부터 n-1까지 row와 col을 반복해서 각각에 현재 인덱스의 점프거리를 추가해서 새로운 r(아래쪽 점프)과 c(오른쪽 점프)로 만들고 새로운 행에 그 전 dp의개수를 추가해주는 방식으로 구현했다.

import sys
input = sys.stdin.readline
n=int(input())
ary = [list(map(int,input().split())) for _ in range(n)]
p = [[0 for _ in range(n)] for __ in range(n)]
p[0][0]=1

for row in range(n):
  for col in range(n):
    if row==n-1 and col==n-1:
      break
    r=row+ary[row][col]
    if r <n:
      p[r][col]+=p[row][col]
    c=col+ary[row][col]
    if c <n:
      p[row][c]+=p[row][col]
print(p[n-1][n-1])