다이나믹 프로그래밍 문제

전에 계산한 값들을 기반으로 현재 값을 구하면 된다

31, 32번 모두 비슷한 유형의 문제

dp문제는 그림을 그려 푸는 게 점화식 세우기 쉬운 듯 하다

 

 

31. 금광

import sys
input=sys.stdin.readline
 
for _ in range(int(input().rstrip())):
    #n*m
    n, m=map(int, input().split())
    arr=list(map(int, input().split()))
    d=[]
 
    i=0
    d.append([0]*m)
    for _ in range(n):
        d.append(arr[i:i+m])
        i+=m
    d.append([0] * m)
    # print(d)
 
    for i in range(1, m):
        for j in range(1, n+1):
            d[j][i]=d[j][i]+max(d[j-1][i-1], d[j][i-1], d[j+1][i-1])
    # print(d)
 
    result=0
    for k in range(1, n+1):
        if result<d[k][-1]:
            result=d[k][-1]
    print(result)
 

 

 

 

32. 정수 삼각형

www.acmicpc.net/problem/1932

import sys
input=sys.stdin.readline
 
n=int(input())
d=[]
for _ in range(n):
    d.append(list(map(int, input().split())))
 
for j in range(n):
    for i in range(j+1):
        #왼쪽이 없음 #up, left_up
        if i-1<0:
            left_up=0
        else:
            left_up=d[j-1][i-1]
 
        #위가 없음
        if i==j:
            up=0
        else:
            up=d[j - 1][i]
 
        #위로 가거나 왼쪽위로 가거나
        d[j][i]=d[j][i]+max(up, left_up)
 
print(max(d[-1]))