[백준 15486번 / C++] 퇴사 2

dp를 활용한 문제이다

 

#접근방법

본인이 생성한 dp 배열의 의미는 해당 인덱스 값에 받을 수 있는 최댓값이다. 

즉, dp[3] = 4 라는 것은 3일에 받을 수 있는 최댓값이다. 

 

이 문제의 핵심은 1일에 상담을 시작하면 3일이 걸리니 받을 수 있는 금액은 4일에 받을 수 있다는 것이다. 

다시 말해서, 1일에는 아직 금액을 받지 못하고 1일+3일 후에야 P1의 비용을 받을 수 있다. 

 

즉, dp[1] 은 0이고 dp[4] = 10 이 되는 것이다. 

dp[2] = 0 이고, dp[7] = 20 

dp[3] = 0 이고, dp[4] = 10이다. 

 

이때, dp[4] 는 day가 1일일 때 dp[day(1일)+T1(3일)] = 10 라는 값이 세팅 되어 있으므로, 

dp[i+Ti] = max(dp[i+Ti], 현재까지의 비용최댓값 + Pi ) 라는 코드로 작성할 수 있다. 

 

즉, dp[4] = 10 으로 이미 세팅되어 있지만 

dp[3+1] = max( 10, 0 + 10) = 10 이 된다. 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	ios::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0); 
	int n; cin >> n;
	vector <int> dp(n + 1, 0);
	int result = 0;
	int cur = 0; 
	for (int i = 0; i < n; i++) {
		int day, cost;
		cin >> day >> cost;
		cur = max(cur, dp[i]);
		if (i + day <= n) {		
			dp[i + day] = max(dp[i + day], cur + cost);
			result = max(dp[i + day], result);
		}
	}
	cout << result;
}

 

15486번: 퇴사 2