[백준_11048] 이동하기 python

대각선, 위, 아래를 모두 생각해 줄 필요는 없다.

모든 사탕은 양수이기 때문이다.

초기 설정만 잘 해주면 쉽게 해결할 수 있다.

근데 이거 그리디 아닌가,,?

# n, m 입력
n, m = map(int, input().split())

# grid 설계
grid = [
    list(map(int, input().split())) for _ in range(n)
]

# dp 설계
dp = [
    [0] * m for _ in range(n)
]

# 초기 설정
dp[0][0] = grid[0][0]

# 가로 줄 초기설정
for i in range(1, m):
    dp[0][i] = dp[0][i-1] + grid[0][i]

# 세로 줄 초기설정
for i in range(1, n):
    dp[i][0] = dp[i-1][0] + grid[i][0]

# dp 채워넣기
for i in range(1, n):
    for j in range(1, m):
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]

# 출력
print(dp[-1][-1])