[Algorithm] 다이나믹 프로그래밍 문제 - 금광, 정수 삼각형, 퇴사

금광

T = int(input())
while T:
    n, m = map(int, input().split())
    data = list(map(int, input().split()))
    dp = []
    count = 0
    for i in range(n):
        dp.append(data[count:count + m])
        count += m

    for k in range(1, m):
        for j in range(n):
            # 첫번째 줄
            if i == 0:
                dp[j][k] = dp[j][k] + max(dp[j + 1][k - 1], dp[j][k - 1])
            # 마지막줄
            elif i == n - 1:
                dp[j][k] = dp[j][k] + max(dp[j - 1][k - 1], dp[j][k - 1])
            else:
                dp[j][k] = dp[j][k] + max(dp[j + 1][k - 1], dp[j][k - 1], dp[j - 1][k - 1])

    print(max(dp[n - 1]))

3가지 경우
1) 첫번째 줄 -> 왼쪽이랑 왼쪽 위에서
2) 마지막 줄 -> 왼쪽이랑 왼쪽 밑에서
3) 나머지 -> 왼쪽, 왼쪽 밑, 왼쪽 위

정수 삼각형

n = int(input())

data = [list(map(int, input().split())) for _ in range(n)]

for i in range(1, n):
    for j in range(len(data[i])):
        if j == 0:
            data[i][j] = data[i][j] + data[i - 1][j]
        elif i == j:
            data[i][j] = data[i][j] + data[i - 1][j - 1]
        else:
            data[i][j] = data[i][j] + max(data[i - 1][j], data[i - 1][j - 1])

print(max(data[n - 1]))

대충 계산해보면서 규칙 찾아갔다.

퇴사

n = int(input())

t = []
p = []

for i in range(n):
    T, P = map(int, input().split())
    t.append(T)
    p.append(P)
dp = [0] * (n + 1)
for j in range(n - 1, -1, -1):
	# 시간 안 넘으면
    if t[j] + j <= n:
        dp[j] = max(dp[j + 1], p[j] + dp[j + t[j]])
    else:
        dp[j] = dp[j + 1]

print(dp[0])

시간이 안넘으면
dp[j] = max(dp[j + 1], p[j] + dp[j + t[j]])
로 다음날로 넘겨 이득 받는게 좋은지 아니면 오늘 일을 받고 일을 마치고 나서 또 일을 받는게 더 좋은지 비교
시간 넘으면
dp[j] = dp[j + 1]
바로 다음날