BOJ 15486번 퇴사 2

BOJ : https://www.acmicpc.net/problem/15486

github : https://github.com/junho0956/Algorithm/blob/master/15486/15486/%EC%86%8C%EC%8A%A4.cpp

 

 

퇴사1, 2 의 문제를 혼자 바로 풀수 있는 정도가 되서

너무 행복합니다.

dp는 너무 어려워요 ㅠㅠ

 

퇴사1는 dp를 사용하지않고 dfs 로 간단히 해결가능하지만

퇴사2는 dp를 사용해야 TLE를 벗어날 수 있습니다.

 

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
 
int N;
ll dp[1500001];
pair<int, int> arr[1500001];
 
ll solve(int day) {
    if (day >= N + 1) return 0;
 
    ll& res = dp[day];
    if (res) return dp[day];
 
    ll ans = solve(day + 1);
    if (day + arr[day].first <= N + 1) ans = max(ans, arr[day].second + solve(arr[day].first + day));
 
    return res = ans;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> arr[i].first >> arr[i].second;
 
    ll ans = 0;
    for (int i = 1; i <= N; i++) {
        ans = max(ans, solve(i));
    }
 
    cout << ans;
 
    return 0;
}