[백준] 15486 퇴사 2

15486번: 퇴사 2

 

www.acmicpc.net

풀이

동적 계획법으로 해결해야하는 문제이다. 동적계획법을 위한 배열을 dp[i]라고 했을 때 dp[i]는 i일 까지 받을 수 있는 최대 금액이라고 정해서 해결하였다.

코드

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int t[1500001], m[1500001];
int dp[1500002];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) 
        cin >> t[i] >> m[i];

    int ans = 0;
    for (int i = 1; i <= n + 1; i++) {
        ans = max(ans, dp[i]);
        // 퇴사일을 넘겨서 일을 할 수 없는 경우
        if (i + t[i] > n + 1) continue;
        dp[i + t[i]] = max(dp[i + t[i]], ans + m[i]);
    }
    cout << ans << '\n';
    return  0;
}