February 26, 2023

1890번: 점프

문제 요약

• N * N을 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프
• 각 칸에는 점프 할 수 있는 칸이 정해져 있음
• 가장 오른쪽 칸으로 이동하는 경우의 수
• 4 ≤ N ≤ 100

풀이

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * N for _ in range(N)]

for row in range(N):
    for col in range(N):
        jump = board[row][col]

        if (jump == 0 or ((row, col) != (0, 0) and dp[row][col] == 0)):
            continue

        if (col + jump < N):
            dp[row][col + jump] += 1 if (row, col) == (0, 0) else dp[row][col]

        if (row + jump < N):
            dp[row + jump][col] += 1 if (row, col) == (0, 0) else dp[row][col]

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

• 칸을 왼쪽 위부터 오른쪽 아래로 순회할 경우 각 칸에 진입하는 시점에는 모든 경우의 수가 계산되어있음을 이용
• Dynamic Programming 기법 이용