[python] 금광 (다이나믹 프로그래밍)

- n x m 금광

- 첫 번째 열부터 금 캐기 시작

- m-1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 중 하나의 위치로 이동

- 채굴자가 얻을 수 있는 금의 최대 크기 출력

 

=> 3가지 위치만 고려

1) 왼쪽 위에서 오는 경우

2) 왼쪽 아래에서 오는 경우

3) 왼쪽에서 오는 경우

 

# 테스트 케이스(Test Case) 입력
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)