[Baekjoon] 백준 11048 이동하기 Python

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

 

❗풀이방법

• 1행과 1열은 누적합 계산
• (1, 1)에서부터 DP 계산
  • max(graph[i-1][j], graph[i][j-1], graph[i-1][j-1]) 계산 후 (i, j)에 합하기

 

❗코드

import sys
input = sys.stdin.readline

n, m  = map(int, input().split(" "))

graph = []

for _ in range(n):
    temp = list(map(int, input().split(" ")))
    graph.append(temp)


for i in range(1, n):
    graph[i][0] += graph[i-1][0]

for i in range(1, m):
    graph[0][i] += graph[0][i-1]


for i in range(1, n):
    for j in range(1, m):
        graph[i][j] += max(graph[i-1][j], graph[i][j-1], graph[i-1][j-1])

print(graph[n-1][m-1])