금광

 

해결법

1. 이 문제에서 값을 일차 배열로 준다. 그렇기에 우린 이것을 이차 배열로 바꿔야 한다.

2. 오른쪽과 오른쪽 위, 아래로 이동할 수 있다는 것은 반대로 생각하면 왼쪽과 왼쪽 위, 아래에서 온다는 의미이다.

3. 쭉 더하고 마지막 열 중에서 가장 큰 값을 찾는다.

 

코드

answer = []

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

    dp = []
    index = 0
    for i in range(n):
        dp.append(ary[index:index + m])
        index += m

    for j in range(1, m):
        for i in range(n):
            # 왼쪽 위면 더 위가 없어서 0
            if i == 0:
                left_w = 0
            else:
                left_w = dp[i-1][j-1]
            
            left = dp[i][j-1]

            # 왼쪽 아래면 더 아래가 없어서 0
            if i == n-1:
                left_s = 0
            else:
                left_s = dp[i+1][j-1]

            dp[i][j] = dp[i][j] + max(left_w, left, left_s)

    result = 0
    for i in range(n):
        result = max(result, dp[i][m-1])
    
    answer.append(result)

for i in answer:
    print(i)

일차 배열을 이차 배열로 바꾸는 법을 잘 알아둬야겠다. 

풀이 생각을 하지못해서 교재 풀이 보고 이해한다음 안보고 풀었다ㅠㅠ