BOJ 11048: 이동하기

https://www.acmicpc.net/problem/11048

11048번: 이동하기

이것도 dp를 활용하여 푸는 기본적인 유형이었다. 간단하게 점화식을 짤 수 있었다.

 

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))

dp = [[0]*M for _ in range(N)]
dp[0][0] = arr[0][0]

for i in range(1, N):
    dp[i][0] = dp[i-1][0] + arr[i][0]
for i in range(1, M):
    dp[0][i] = dp[0][i-1] + arr[0][i]

for i in range(1, N):
    for j in range(1, M):
        dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + arr[i][j]

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