https://www.acmicpc.net/problem/3372
코드
n = int(input())
board = [list(map(int, input().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 board[i][j] == 0:
continue
# 오른쪽
if j+board[i][j] < n:
dp[i][j+board[i][j]] += dp[i][j]
# 아래
if i+board[i][j] < n:
dp[i+board[i][j]][j] += dp[i][j]
print(dp[n-1][n-1])
dp[i][j]는 (i, j)까지 갈 수 있는 경로의 수를 저장한다. 출발점인 (0, 0)의 dp값을 1로 놓고, N × N 게임 보드의 각 칸을 살펴보며 현재 칸(i, j)에서 오른쪽과 아래로 board[i][j]만큼 이동할 수 있다면 현재 칸 (i, j)까지 올 수 있는 경로의 수인 dp[i][j]를 이동한 칸의 dp 값에 더해주면 된다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 15990번 1, 2, 3 더하기 5 (0) | 2024.05.23 |
---|---|
[Python/파이썬] 백준 4097번 수익 (1) | 2024.05.15 |
[Python/파이썬] 백준 16432번 떡장수와 호랑이 (0) | 2024.05.04 |
[Python/파이썬] 백준 14430번 자원 캐기 (2) | 2024.04.27 |
[Python/파이썬] 백준 21923번 곡예 비행 (0) | 2024.04.26 |