[ 이것이 취업을 위한 코딩 테스트다 with 파이썬 ] Chapter 16 다이나믹 프로그래밍 문제 - Q31 금광

1. 문제

---

 

2. 코드

def gold_func(n, m, data):
 
    d = [[0] * m for _ in range(n)] 

    for i in range(n):
        d[i][0] = data[i][0]
        
    for j in range(1, m):
        for i in range(n):
            if i+1 < n:
                temp = data[i][j] + d[i+1][j-1]
                d[i][j] = max(d[i][j], temp)
            
            elif i-1 >= 0:
                temp = data[i][j] + d[i-1][j-1]
                d[i][j] = max(d[i][j], temp)
            
            temp = data[i][j] + d[i][j-1]
            d[i][j] = max(d[i][j], temp)
    
    max_list = []

    for i in range(n):
        max_list.append(max(d[i]))

    print(max(max_list))
    

T = int(input())

for i in range(T):
    n, m = map(int, input().split())
    input_data = list(map(int, input().split()))
    
    data = []

    for i in range(0,len(input_data),4):
        data.append(input_data[i:i+4])

    gold_func(n, m, data)