(Python/파이썬) 백준 1890번 - 점프

문제출처: https://www.acmicpc.net/problem/1890

1890번: 점프

1. 코드

n = int(input())
 
way=[]
for i in range(n):
    way.append(list(map(int,input().split())))
 
#해당 좌표 이동가능한 방법의 갯수
dp = [[0 for _ in range(n)] for _ in range(n)]
#시작 지점 1로 지정
dp[0][0] = 1
 
for y in range(n):
    for x in range(n):
        if way[y][x]==0:
            break
        now = way[y][x]
        #오른쪽 이동
        if x+now <n:
            dp[y][x+now] += dp[y][x]
        #아래로 이동
        if y+now <n:
            dp[y+now][x] += dp[y][x]
 
print(dp[y][x])

2. 해결과정

좌표가 (0,0) 부터 (n-1,n-1)까지 순회하면서 현재좌표(x,y)에 오른쪽 or 아래쪽으로 갈 수 있는지 검사를 해주고, 갈 수 있다면 dp[x+now][y+now]에 dp[y][x]를 더해준다. dp는 해당 좌표로 이동가능한 방법의 갯수를 담아준다. 시작지점을 1로 초기화해서 시작해주면 된다.

도착지점이 0일때 break해주면 된다.