[백준] 11048번 이동하기

💡문제접근

• 현재 지점에서 오른쪽 한칸, 아래 한칸, 오른쪽 대각선 아래 한칸 이동할 수 있으므로 왼쪽과 위쪽 라인에 0을 추가해줘서 IndexError를 방지했다.
• DP문제치곤 쉬워서 매우 간단하게 풀었다.

💡코드(메모리 : 78588KB, 시간 : 856ms)

import sys
input = sys.stdin.readline

N, M = map(int, input().strip().split())
maze = [list(map(int, input().strip().split())) for _ in range(N)]
dp = [[0] * (M+1) for _ in range(N+1)]

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

💡소요시간 : 10m