이것이 코딩테스트다 31 금광

문제 링크

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

---

Test Case

입력
2
3 4
1 3 3 2 2 1 4 1 0 6 4 7
4 4
1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2

출력
19
16

---

문제 풀이

m 개 간격으로 입력을 받은 list를 나누서 dp 배열에 저장한다. 그 뒤에 반복문으로 각 세로줄을 검토하면서 제일 상단, 하단, 그리고 중간에 있는 값들을 더하면서 최대값으로 dp 배열을 채워서 문제를 풀었다. 각 세로줄을 검토할 때 상단, 하단, 중간을 나누는 개념이 어렵지않다고 생각했는데 또 마냥 그렇게 쉽지만은 않은 문제라고 생각한다.

---

Source Code

import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    n,m = map(int, input().split())
    data = list(map(int, input().split()))
    dp = []
    index = 0
    for _ in range(n):
        dp.append(data[index:index+m])
        index += m
    
    for j in range(1, m):
        for i in range(n):
            # 상단
            if i == 0: 
                dp[i][j] = max(dp[i][j-1] + dp[i][j], dp[i+1][j-1] + dp[i][j])
            # 하단
            elif i == n-1: 
                dp[i][j] = max(dp[i-1][j-1] + dp[i][j], dp[i][j-1] + dp[i][j])
            # 중단
            else: 
                dp[i][j] = max(dp[i-1][j-1] + dp[i][j], dp[i][j-1] + dp[i][j], dp[i+1][j-1] + dp[i][j])
        
    ans = 0
    for i in range(n):
        ans = max(ans,dp[i][m-1])
    print(ans)