[백준/Python] 11048번 - 이동하기

문제

백준 11048번 - 이동하기

해결 과정

• DP를 활용하여 풀기
• DP[i][j]는 그 전에 왼쪽, 위, 왼쪽 위 대각선에서 올 때 가장 큰 값을 넣는다.
  즉 반대로 !!!!
• 점화식
  dp[i][j] = graph[i - 1][j - 1] + max(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])
  • graph[i - 1][j - 1] 그래프는 0,0부터 n-1,m-1까지 있음
• dp = [[0] * (m + 1) for i in range(n + 1)]
  • 위 아래로 한칸씩 더 추가해준 이유는 맨 위의 숫자들과 맨 왼쪽의 숫자들도 똑같이 비교를 할 수 있게 하기 위해서
• 그래프
  
• DP
  

풀이

import sys

n,m = map(int,sys.stdin.readline().split())

graph = []
for _ in range(n):
  graph.append(list(map(int,sys.stdin.readline().split())))

dp = [[0] * (m + 1) for i in range(n + 1)]

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


print(dp[n][m])

https://pacific-ocean.tistory.com/204