[Python] 이동하기 - 백준 (DP)

해당 글은 백준 11048번 문제 '이동하기'을 다룬다.

문제

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

11048번: 이동하기

 

설명

해당 문제는 DP로 해결할 수 있다.

DP로 (n, m)까지 3가지 방향으로 이동하면서, 사탕을 가장 많이 가져갈 수 있는 값으로 업데이트한다.

 

코드

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(n):
    for j in range(m):
        if i + 1 < n:
            dp[i + 1][j] = max(dp[i][j] + arr[i + 1][j], dp[i + 1][j])
        if j + 1 < m:
            dp[i][j + 1] = max(dp[i][j] + arr[i][j + 1], dp[i][j + 1])
        if i + 1 < n and j + 1 < m:
            dp[i + 1][j + 1] = max(dp[i][j] + arr[i + 1][j + 1], dp[i + 1][j + 1])
            
print(dp[n-1][m-1])