문제

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.

준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.

준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.

입력

첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)

둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며, r번째 줄의 c번째 수는 (r, c)에 놓여져 있는 사탕의 개수이다. 사탕의 개수는 0보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수를 출력한다.

역시 초보는 어쩔 수 없다. 다이내믹 프로그래밍 문제는 늘 어렵다. 한참을 헤매다 점화식을 못 구하고 인터넷의 도움을 받았다. 먼저 푼 이들의 설명을 보고 나서야 어렴풋이 이해할 수 있었다. 아직 갈 길이 멀다.

1. m+1개의 0으로 구성된 리스트가 n+1개만큼 들어 있는 리스트 dp를 만든다.
2. (왼쪽 위) 대각선+위 또는 대각선+아래(ㄱ 또는 ㄴ의 합) 가운데 큰 값을 대각선 값과 더한 값을 구한다. 이런 식으로 리스트(l) 끝까지 ↘ 방향으로 가장 큰 값을 구해 나간다.
3. 리스트 마지막 값(l[n][m])이 미로에서 가져올 수 있는 사탕 개수의 최대값이다.

점화식

dp[n][m] = l[n-1][m-1] + max(dp[n][m-1], dp[n-1][m], dp[n-1][m-1])

결과 코드는 아래와 같다.

n, m = map(int, input().split())
l = []
for _ in range(n):
    r = list(map(int, input().split()))
    l.append(r)
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] = l[i-1][j-1] + max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
print(dp[n][m])

[문제 보기]