[백준 BOJ_1890] 점프 Python 풀이

출처: 백준 온라인 저지

문제

풀이

동적계획법으로 풀었습니다.

cache는 다음과 같습니다:

좌표가 (x, y)일 때,
cache[i][j] = 좌표 (j, i)까지 갈 수 있는 경로의 수

출발 지점인 (0, 0)에는 1을 저장해주어 시작합니다. 각 좌표를 돌아주며 해당 좌표까지 가는 길이 있고 (cache[i][j]가 0이 아닌 경우) 해당 좌표에서 갈 수 있는 거리가 0이 아니라면 갈 수 있는 좌표의 cache를 업데이트 해줍니다.

jump만큼 오른쪽, 그리고 아래쪽으로 갈 수 있다면(jump를 더한 값이 N보다 작다면) 해당 좌표의 cache에 cache[i][j]를 더해줍니다.

마지막에는 도착 좌표인 cache[N-1][N-1]를 출력해줍니다.

코드

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
cache = [[0 for _ in range(N)] for _ in range(N)]
cache[0][0] = 1

for i in range(N):
  for j in range(N):
    jump = graph[i][j]
    if not cache[i][j] or not jump:
      continue
    if i + jump < N:
      cache[i+jump][j] += cache[i][j]
    if j + jump < N:
      cache[i][j+jump] += cache[i][j]
print(cache[N-1][N-1])