197. 퇴사

백준

1. 다이나믹 프로그래밍

n = int(input())
t = []
p = []
dp = [0] * (n + 1)
max_value = 0

for _ in range(n):
  x, y = map(int, input().split())
  t.append(x)
  p.append(y)

#리스트를 뒤에서부터 거꾸로 확인
for i in range(n - 1, -1, -1):
  time = t[i] + i
  #상담이 기간 안에 끝나는 경우
  if time <= n:
    dp[i] = max(p[i] + dp[time], max_value)
    max_value = dp[i]

  else:
    dp[i] = max_value

print(max_value)

2. C++

#include <bits/stdc++.h>

using namespace std;

int n; // 전체 상담 개수
vector<int> t; // 각 상담을 완료하는데 걸리는 기간
vector<int> p; // 각 상담을 완료했을 때 받을 수 있는 금액
int dp[16]; // 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화
int maxValue;

int main(void) {
    cin >> n;

    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        t.push_back(x);
        p.push_back(y);
    }

    // 리스트를 뒤에서부터 거꾸로 확인
    for (int i = n - 1; i >= 0; i--) {
        int time = t[i] + i;
        // 상담이 기간 안에 끝나는 경우
        if (time <= n) {
            // 점화식에 맞게, 현재까지의 최고 이익 계산
            dp[i] = max(p[i] + dp[time], maxValue);
            maxValue = dp[i];
        }
        // 상담이 기간을 벗어나는 경우
        else dp[i] = maxValue;
    }

    cout << maxValue << '\n';
}