[백준] 11048 - 이동하기 / Python / 실버 2

🚩문제 주소

📄풀이

다이나믹 프로그래밍

계산하기 편하게 하기 위해 배열의 첫째 줄과 각 줄의 첫번째 숫자로 0을 추가합니다.

배열을 순회하면서

현재 탐색한 자리의 숫자 + 현재 탐색한 자리의 숫자의 위쪽
현재 탐색한 자리의 숫자 + 현재 탐색한 자리의 숫자의 왼쪽
현재 탐색한 자리의 숫자 + 현재 탐색한 자리의 숫자의 좌상단 대각선

중에서 가장 큰 값을 현재 자리의 숫자로 업데이트 합니다.

업데이트한 배열의 마지막 줄에서 가장 큰 숫자를 찾아서 출력합니다.

👨‍💻코드

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
maze = [[0]*(M+1) for _ in range(N+1)]
for n in range(N):
  for m in range(M):
    maze[n+1][m+1] = arr[n][m]

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

print(max(maze[-1]))