금광

문제

n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m - 1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요.

입력조건

• 첫째 줄에 테스트 케이스 T가 입력됩니다. (1 <= T <= 1000)
• 매 테스트 케이스 첫째 줄에 n과 m이 공백으로 구분되어 입력됩니다. (1 <= n, m <= 20) 둘째 줄에 n x m개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력됩니다. (1 <= 각 위치에 매장된 금의 개수 <= 100)

출력조건

• 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력합니다. 각 테스트 케이스는 줄 바꿈을 이용해 구분합니다.

입력 예시

2
3 4
1 3 3 2 2 1 4 1 0 6 4 7
4 4
1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2

출력 예시

19
16

풀이방식

해당 문제는 항상 첫 번째 열부터 출발을 하는 겁니다. 첫 번째 열부터 금광을 캘 수 있는 방법은 오른쪽 위, 오른쪽, 오른쪽 아래를 이동하는 겁니다. 여기서 중요한 포인트는 가장 위의 행에서는 오른쪽, 오른쪽 아래로만 이동이 가능하고, 가장 아래 행에서는 오른쪽, 오른쪽 위로만 이동이 가능합니다. 다이나믹 프로그래밍은 dp 배열의 의미를 설정하는 것이 가장 중요합니다. 이를 토대로 bottom-up이 가능하기 때문입니다. 이제 dp 배열의 정의를 해야할 것 같습니다. 제가 설정한 dp 배열은 아래와 같습니다.

dp[i][j]: i, j까지 이동했을 때 얻을 수 있는 가장 많은 금광값

그렇다면 dp[1][1]은 1, 1까지 이동했을 때 얻을 수 있는 가장 많은 금광값이 저장되어 있을 겁니다. 우리는 오른쪽 위, 오른쪽, 오른쪽 아래로만 이동이 가능하기 때문에 아래와 같은 점화식을 도출할 수 있습니다.

dp[i][j] = array[i][j] + max(dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1])

코드

import sys

def dynamicProgramming():
    maxNum = 0
    dp = [[0] * m for _ in range(n)]  # dp[i][j]는 i, j까지 이동했을 때 얻을 수 있는 가장 많은 금광값
    dp[0][0] = array[0][0]
    dp[1][0] = array[1][0]
    dp[2][0] = array[2][0]

    for i in range(1, m):  # 첫번째 열부터 비교
        for j in range(n):  # 첫번째 행부터 비교
            if j == 0:  # 가장 첫번째 행에 있다면 오른쪽과 오른쪽 아래 비교
                dp[j][i] = max(dp[j][i - 1] + array[j][i], dp[j + 1][i - 1] + array[j][i])
            elif j == n - 1:  # 가장 마지막 행에 있다면 오른쪽과 오른쪽 위 비교
                dp[j][i] = max(dp[j - 1][i - 1] + array[j][i], dp[j][i - 1] + array[j][i])
            else:  # 중간행에 있다면 오른쪽, 오른쪽 아래, 오른쪽 위 비교
                dp[j][i] = max(dp[j - 1][i - 1] + array[j][i], dp[j][i - 1] + array[j][i], dp[j + 1][i - 1] + array[j][i])

    # 가장 큰 값 추출
    for item in dp:
        for num in item:
            if num >= maxNum:
                maxNum = num
    return maxNum


T = int(sys.stdin.readline().strip())
for _ in range(T):
    n, m = map(int, sys.stdin.readline().split())
    data = list(map(int, sys.stdin.readline().split()))
    idx = 0
    array = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            array[i][j] = data[idx]
            idx += 1
    result = dynamicProgramming()
    print(result)