PS
[백준] 15486번 퇴사 2 C++
Eastplanet
2022. 6. 28. 17:24
문제 출처: https://www.acmicpc.net/problem/15486
15486번: 퇴사 2
첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)
www.acmicpc.net
Top-down 방식으로 오늘 상담을 하는경우 or 오늘 상담을 하지 않는 경우를 비교하여 더 큰 값으로 갱신하며 최대 금액을 구함.
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <string>
using namespace std;
int dp[1500001];
int T[1500001];
int P[1500001];
int N;
int job(int idx) {
if (idx == N)return 0;
if (dp[idx] != -1)return dp[idx];
int val = job(idx + 1);
if (idx + T[idx] <= N)
val = max(val, job(idx + T[idx]) + P[idx]);
dp[idx] = val;
return val;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> T[i] >> P[i];
}
fill(&dp[0], &dp[1500001], -1);
cout << job(0);
}