[백준] 1890 - 점프 with.Python

💡문제 분석 요약

-- 문제 --

입력 : 게임 판의 크기 N (4 ≤ N ≤ 100)

• 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프

• 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리

• 오른쪽이나 아래쪽으로만 이동

• 0은 더 이상 진행을 막는 종착점

• 한 번 점프를 할 때, 방향을 바꾸면 안 됨

• 경로의 개수를 구하는 프로그램

💡알고리즘 설계

💡코드

💡시간복잡도

O(N*N)

💡틀린 이유

💡틀린 부분 수정 or 다른 풀이

(https://fre2-dom.tistory.com/410 풀이 참고하였습니다.)

import sys

n = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().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 i == n - 1 and j == n - 1:
            print(dp[i][j])
            break

        # 오른쪽으로 이동
        if j + graph[i][j] < n:
            dp[i][j + graph[i][j]] += dp[i][j]

        # 아래로 이동
        if i + graph[i][j] < n:
            dp[i + graph[i][j]][j] += dp[i][j]

💡느낀점 or 기억 할 정보

1. 처음 코테를 접하다보니 접근하는데 어려움을 느낌. -> 문제 많이 접해보기.

2. 개념만 공부하지 말고 기본 구현한 코드 많이 접해보기.

3. dp[i][j]는 좌표 (i, j)까지 도달할 수 있는 경로의 수

4. j + graph[i][j]: 현재 위치에서 오른쪽으로 이동할 칸의 인덱스