(C++) - 백준(BOJ) 15486번 : 퇴사 2

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

15486번: 퇴사 2

dp 문제였습니다.

 

 

📕 풀이방법

 수행 시간이 n이 150만이므로 O(n)에 수행해야 합니다. 제한사항이 영향을 끼치지 않기 때문에 본질적으로 퇴사문제와 풀이 방법이 같습니다.

 

 

제 풀이는 해당 문제에 대한 설명을 포스팅 한 글로 대체합니다.

 

https://codecollector.tistory.com/1113

(C++) - 백준(BOJ) 14501번 : 퇴사

---

 

📕 Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
struct Consulting {int t, p; };
int n, d[1500001];
vector <Consulting> consult;

int dp(int i){
    if(i >= n) return 0;
    int &ret = d[i];
    if(ret != -1) return ret;
    ret = 0;
    if(i + consult[i].t <= n) ret = max(ret,dp(i+consult[i].t) + consult[i].p);
    ret = max(ret, dp(i+1));
    return ret;
}
int main(){
    memset(d,-1,sizeof(d));
    fastio;
    cin >> n;
    consult.resize(n);
    for(int i = 0,t,p; i < n; i++) cin >> t >> p, consult[i] = {t,p};
    cout << dp(0);
}