문제

문제 출처

문제 해결 전략

동적 프로그래밍을 이용하여 문제를 해결하면 좋겠다는 생각을 우선 했다.
예시를 들어서 설명을 해보면,

입력 값
7
3 10 0
5 20 1
1 10 2
1 20 3
2 15 4
4 40 5
2 200 6

i가 시작 인덱스라고 했을 때, //i는 커서 같은 역할
i = 0에서 시작
total time = 0 + T0 = 3 / reward = 10
인덱스 3으로 이동

tot = 3 + T3 = 4 / reward = 10 + 20 = 30

인덱스 4로 이동
tot = 4 + 2 = 6 / reward = 30 + 15 = 45

dp 방식을 이용
만약 일을 진행하는데 주어진 날보다 초과되면 dp[i+1] 값을 취해준다.
주어진 날 내에 끝낼 수 있다면 dp[i] = max(dp[i+t[i]]+p[i], dp[i+1]) 수행
위 점화식을 풀어 설명해보면 dp[i+t[i]] +p[i]는 i번째 상담을 수행하면 t[i]일간 상
담을 못하고 p[i]의 금액을 얻을 수 있고, dp[i+1]은 i번째 상담을 수행하지 않으면
그 전단계 역으로 가기 때문에 전단계인 dp[i+1]으로 갱신되게 된다.
그렇게 마지막 단계인 dp[1]이 얻을 수 있는 최대 수익이 된다.

코드

#include<iostream>
#include<vector>
using namespace std;
int t[16];
int p[16];
int dp[16];

int main(){

	int n; cin >> n;

	for(int i = 1;i <= n;i++){ cin >> t[i] >> p[i]; }

	for(int i = n;i >= 1;i--){
		if(i + t[i] - 1 > n){
			dp[i] = dp[i+1];
			continue;
		}
		dp[i] = max(dp[i+t[i]]+p[i], dp[i+1]);
		//cout << "DP :" << dp[i] << endl;
	}

	cout << dp[1] << '\n';
	return 0;
}