백준 14501. 퇴사

https://www.acmicpc.net/problem/14501

 

1. DP 탑다운 - 1

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

# T(걸리는 기간), P(수익)

dp = [-1] * (n+1) # 0일부터 n일까지 얻을 수 있는 최대 수익 저장 테이블

# f함수는 idx(현재 날짜)부터 얻을 수 있는 최대 수익을 반환하는 함수
def f(idx):
    if idx >= n:  # 현재 날짜가 퇴사 날짜를 넘으면 더 이상 상담할 수 없으므로 0 반환
        return 0

    if dp[idx] != -1:  # 이미 저장되었다면 -> 중복계산 방지
        return dp[idx]

    # 상담을 받는 경우와 안 받는 경우를 비교해서 최댓값을 dp에 저장!
    if idx + arr[idx][0] <= n:  # 상담이 퇴사일을 넘기지 않는 경우에만 상담 가능
        dp[idx] = max(f(idx + arr[idx][0]) + arr[idx][1], f(idx + 1))
    else:  # 상담을 퇴사일까지 끝낼 수 없는 경우 -> 상담 안 받고 넘어감
        dp[idx] = f(idx + 1)

    return dp[idx]

print(f(0))

2. DP 탑다운 - 2

import sys
input = sys.stdin.readline()
n = int(input())

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

dp = [0] * (n+1)

for i in range(n-1, -1, -1):
    # i일에 상담하는 것이 퇴사일을 넘기면 상담 x
    if i + arr[i][0] > n:
        dp[i] = dp[i+1]
    else:
        # i일에 상담(i일의 수익 + i일에 상담 후의 최대수익) vs i일에 상담 안함(i+1일의 수익) 중 최댓값
        dp[i] = max(arr[i][1]+dp[i+arr[i][0]], dp[i+1])

print(dp[0]) # 0일부터 얻을 수 있는 최대수익 출력

3-1. DP 바텀업( 바텀업 방식은 작은 문제부터 차례대로 해결해 나가면서 더 큰 문제를 해결하는 방식!)

# 특정 날의 상담을 선택하면 그 상담이 끝나는 날 이후에 얻을 수 있는 수익을 
# 그 전까지의 수익과 비교해 최댓값을 갱신하는 방식

import sys
input = sys.stdin.readline()
n = int(input())

arr = [list(map(int,input().split())) for _ in range(n)] # ?일까지의 최대 수익 기록

dp = [0] * (n+1)

for i in range(n):  # i는 현재 상담을 고려할 날짜
    for j in range(i + arr[i][0], n + 1):  # i날에 상담을 진행했을 때, 그 상담이 끝나는 시점(j)
        if dp[j] < dp[i] + arr[i][1]:  # i번째 상담을 했을 때의 수익이 더 크다면 갱신
            dp[j] = dp[i] + arr[i][1]  # 더 큰 수익으로 dp[j] 갱신

print(dp[-1]) # n일(퇴사일)까지의 최대 수익

3-2. DP 바텀업

N = int(input())
arr = [[] for _ in range(N)]
for i in range(N):
    a, b = map(int, input().split())
    arr[i] = [a, b]

dp = [0 for _ in range(N+1)] # N+1인 이유는 퇴사 이후 수익(0)도 고려해야 하기 때문!

for idx in range(N)[::-1]: # 마지막 날부터 첫번째 날까지 거슬러 올라감(N-1, N-2, ...0)
    if idx + arr[idx][0] > N : # 일을 퇴사일 전에 끝낼 수 없다면 상담을 할 수 없음 -> 그 전 날의 보상을 유지
        dp[idx] = dp[idx + 1]
    else : # 상담이 가능한 경우, 상담을 받는 경우와 받지 않는 경우 비교해서 최댓값 저장
        dp[idx] = max(dp[idx + arr[idx][0]] + arr[idx][1], dp[idx + 1])

print(dp[0]) # 첫날부터 최대한 얻을 수 있는 수익을 뜻함