(Python/파이썬) 백준 11048번 - 이동하기

문제출처: https://www.acmicpc.net/problem/11048

11048번: 이동하기

1. 코드

n,m = map(int, input().split())
maze =[]
 
for _ in range(n):
    maze.append(list(map(int, input().split())))
 
dp =[[0]*(m+1)]*(n+1)
 
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j]=max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+maze[i-1][j-1]
 
print(dp[n][m])

2. 해결과정

이차원 배열을 설정해서, maze라는 배열에 사탕의 갯수를 입력받는다.

dp에는 각 자리에 올 수 있는 가장 많은 갯수를 담아주면 되는데. 오른쪽, 밑, 오른쪽 밑 대각선으로 움직일 수 있기 때문에 반대로, 왼쪽, 위, 왼쪽 위 대각선의 dp값을 비교해서 가장 큰 max값과 더해주면 원하는 값을 구할 수 있다.

 

3. 느낀점

dp문제는 점화식만 찾으면 풀 수 있을 것 같은 문제가 많은 것 같다..