[DP] 금광

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 30분

1. 문제 설명

- 리스트가 주어지면 해당 리스트를 NxM행렬로 만들고 최대가 되는 값을 리턴한다. 

2. 접근 방식

1) 들어오는 input을 행과 열로 나눈다.

2) 첫 행부터 되는 경우를 다 확인해가며 ls값을 확인한다.

3. 코드

import numpy as np
T = int(input())

for _ in range(T):
    n, m = map(int, input().split())
    gold = list(map(int, input().split()))
    nmgold = np.array(gold).reshape(n, m).tolist()
    tmp = [[0] * m for _ in range(n)]
    for i in range(n):
        tmp[i][0] = nmgold[i][0]
    for j in range(1, m): # 1열 ~ 4열
        for i in range(n): # 1행에서 가능한 것
            left_up = 0 if i==0 else i-1
            left_mid = i
            left_down = 0 if i == (n-1) else i+1 
            tmp[i][j] = nmgold[i][j] + max(tmp[left_up][j-1], tmp[left_mid][j-1], tmp[left_down][j-1])
    print(max(map(max, tmp)))

4. 코멘트

- 점화식을 안 만들고 해서 어려웠던 거 같다. 확실히 DP는 점화식을 세워야 문제 풀이가 편하다.
- 점화식 세우는 연습이 필요하다.