boj 1890 : 점프

문제 주소: https://www.acmicpc.net/problem/1890

난이도: silver 2

1.문제설명

• 2차원 보드가 주어진다.
• 각 칸에는 숫자가 써있는데 그 숫자만큼 아래 or 오른쪽으로 이동가능하다
• 가장 왼쪽 윗칸에서 가장 오른쪽 아랫칸으로 갈수있는 경우의 수를 구해라

2.문제해결 아이디어.

• 그래프 탐색 같기도해서 dfs해보니깐 시간초과 떴다.
• dp로 해보자
• 2차원 dp테이블 만들어서 각 원소값은 해당 위치까지 갈수있는 경우의 수

3.문제접근법

• dp 테이블 생성

dp = [[0]*N for i in range(N)]
dp[0][0] = 1

• dp 테이블 값 업데이트

for i in range(N):
    for j in range(N):
        if i == N-1 and j == N-1: #가장 오른쪽 아랫칸 도착하면 중지
            break
        else:
            down = i + board[i][j] #아랫칸으로 숫자만큼 이동할 경우 인덱스
            right = j + board[i][j] #오른쪽칸으로 숫자만큼 이동할 경우 인덱스

            if down < N: #범위안에 있으면
                dp[down][j] += dp[i][j]
            if right < N: #범위안에 있으면
                dp[i][right] += dp[i][j]

4.특별히 참고할 사항

• 시간복잡도는 O(N^2)

5.코드구현

import sys
input = sys.stdin.readline

N = int(input())
board = []
for i in range(N):
    _temp = list(map(int, input().split()))
    board.append(_temp)

dp = [[0]*N for i 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:
            break
        else:
            down = i + board[i][j]
            right = j + board[i][j]

            if down < N:
                dp[down][j] += dp[i][j]
            if right < N:
                dp[i][right] += dp[i][j]
print(dp[N-1][N-1])