금광 다이나믹프로그래밍

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

대표적인 다이나믹프로그래밍 문제입니다. 우리가 문제를 풀때 일정한 규칙에 따라서 점화식을 구할 수가 있는데 이번 금광 문제도 마찬가지 입니다. 다음 칸으로 넘어 갈때 가장 큰 값을 선택하면 됩니다.

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

또한 공간복잡도에 있어서도 다른 테이블을 만들지 않고 기존 테이블에 그대로 덮어 씌우면서 진행을 할 수 있습니다.

#테스트 케이스 입력
for tc in range(int(input())):
    #금광 정보 입력
    n, m = map(int, input().split())
    array = list(map(int,input().split()))
    
    #다이나믹 프로그래밍을 위한 2차원 DP테이블 초기화
    dp = []
    index = 0
    for i in range(n):
        dp.append(array[index:index+m])
        index += m
    
    #다이나믹 프로그래밍 진행
    for j in range(1,m):
        for i in range(n):
            #왼쪽에서 오는 경우
            if i == 0:
                left_up = 0
            else:
                left_up = dp[i-1][j-1]
            #왼쪽아래에서 오는 경우
            if i == n - 1:
                left_down = 0
            else:
                left_down = dp[i+1][j-1]
            #왼쪽에서 오는 경우
            left = dp[i][j-1]
            dp[i][j] = dp[i][j] + max(left_up, left_down, left)
    
    result = 0
    for i in range(n):
        result = max(result, dp[i][m-1])
    
    print(result)

바로 다이나믹프로그래밍을 진행하는 부분을 보겠습니다.

i가 0이라면(왼쪽에서 첫번째 숫자라면) 왼쪽에서 올 수 있는 경우는 없으니 0이 되고 아니라면 왼쪽 위에서 오는 경우를 하나 넣고 이런식으로 총 3가지의 경우의 수를 만들고 max값을 계산해서 dp에 바로 넣어줍니다.