백준 15468 - 퇴사 2

www.acmicpc.net/problem/15486

15486번: 퇴사 2

 

상담을 통해 백준이가 얻을 수 있는 최대 수익을 구해보자.

N이 최대 150만으로 꽤 크므로 완전탐색은 불가능하고 동적 계획법을 통해 문제를 풀어야 한다.

 

다음 점화식을 세워 풀이할 수 있다. 구하려는 최대 수익 earning에 대해

earning += max(idx 일에 상담을 실시 했을 때 벌 수 있는 수익, idx 일에 상담을 하지 않을 경우 벌 수 있는 수익)

본인의 코드에서는 이를 탑다운으로 구현하였다.

 

전체코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll dp[1500000];
vector<pair<int, int>> task;
int n;

ll schedule(int idx);

int main()
{
    memset(dp, -1, sizeof dp);
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;

    for (int i = 0; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;
        task.push_back({a, b});
    }
    
    cout << schedule(0);
}

ll schedule(int idx)
{
    if (idx == n)
        return 0;

    if (dp[idx] != -1)
        return dp[idx];
    
    dp[idx] = 0;
    
    ll &ret = dp[idx];
    
    if (idx + task[idx].first <= n)
        ret += max(schedule(idx + 1), task[idx].second + schedule(idx + task[idx].first));
    else
        ret += schedule(idx + 1);
    
    return ret;
}