[백준] 1890 - 점프

1. 문제

1890번: 점프

2. 개요

dp 문제.

진행방향은 아래, 오른쪽으로 제한되고 보드에 쓰인 칸 만큼 움직일 수 있을 때

좌상단에서 우하단까지 갈 수 있는 경우의 수를 구하면 된다.

3. 코드 및 추가내용

import sys

N = int(sys.stdin.readline())

board = []
dp = []
for i in range(N):
    board.append(list(map(int, sys.stdin.readline().split())))
    dp.append([0 for j in range(N)])

dp[0][0] = 1

dirY, dirX = [1, 0], [0, 1]

for i in range(N):
    for j in range(N):
        if i == j == N-1:
            continue

        for k in range(2):
            nextY, nextX = i + board[i][j] * dirY[k], j + board[i][j] * dirX[k]

            if nextY < 0 or nextY >= N or nextX < 0 or nextX >= N:
                continue

            dp[nextY][nextX] += dp[i][j]

print(dp[-1][-1])

dp 시작점을 1로 두고 시작한다.

모든 칸을 탐색하며 갈 수 있는 칸에 현재 칸의 경우의 수를 더해간다.

최종 도착지점을 제외한 모든 칸에 대해 작업을 마치고 도착지점의 값을 출력한다.