[이코테] 금광

t = int(input())

result = []

for i in range(t):
    n, m = map(int,input().split())
    input_data = list(map(int,input().split()))

    max_value = 0
    
    array = [[0]*21 for _ in range(21)]
    dp = [[0]*21 for _ in range(21)]

    for i in range(n):
        for j in range(m):
            array[i][j] = input_data[(i*m)+j]

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

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

            if dp[j][i] > max_value:
                max_value = dp[j][i]
    
    result.append(max_value)


for i in result:
    print(i)

이번 문제는 n x m 크기의 금광이 있을 때, 첫번째 열에서 오른쪽으로 이동하면서 얻을 수 있는 금의 최대 크기를 구하는 문제이다.

 

문제를 읽자마자 모든 경우의 수를 구하는 것이 아니라, DP 알고리즘을 사용하여 Bottom-Up 방식으로 문제를 풀이해야겠다는 생각이 들었고, DP 테이블을 채우는 기준(점화식)은 다음과 같았다.

 

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

 

위와 같은 점화식이 나오게 된 이유는, 열을 기준으로 오른쪽 위, 오른쪽, 오른쪽 아래로만 이동할 수 있기 때문이다.

 

문제를 풀이하는 방법을 떠올리는 것은 어렵지 않았는데 '입력 값을 2차원 리스트로 저장하는 것'과 '리스트 범위를 벗어나지 않도록 DP 테이블의 여유 공간을 만들어주는 것'에서 시간을 많이 잡아먹게 되었다.

 

그리고 행이 아니라 열을 기준으로 이동하고, 점화식 또한 이전 열의 값들을 기준으로 하기 때문에 행이 아니라 열을 기준으로 계산을 진행해야했다.

 

DP 알고리즘을 풀이할 때 index의 범위나 값이 헷갈리지 않도록 하기 위해서는 'DP 테이블의 공간을 여유롭게 만들어어야 하는 것'과 'DP 테이블을 채우는 순서와 방식을 정확하게 파악'해야 틀리는 일이 없게 된다는 것을 느낄 수 있던 문제였다 :)