문제 출처

1. 문제설명

• N+1일째 되는 날 퇴사를 하기 위해서 남은 N일 동안 최대한 많은 상담을 하려고 한다.
• 각 상담은 상담을 완료하는데 걸리는 기간 $T_i$와 상담 금액 $P_i$로 이루어져 있다.
• 상담을 적절히 했을 때, 얻을 수 있는 최대 수익을 구하라

2. 알고리즘 설계

• DP 방식으로 풀이할 수 있었다.
• 가장 뒤의 인덱스부터 시작하여 상담을 할 수 있다면 값을 갱신해준다.
  • 만약 일정이 N+1 이상이 되면 상담이 불가능하다.
  • 상담 기간 안에 다른 상담을 진행할 수 없다.
• 상담 기간 안에 들어온다면, 바로 앞의 상담 값과 비교해준다.
  • DP[i] = max(DP[i+T[i]]+P[i], DP[i+1])
• 상담 기간이 불가능하다면 바로 앞의 상담 값으로 갱신한다.
  • DP[i] = DP[i+1]

3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int SZ = 16;
int T[SZ], P[SZ], DP[SZ];
int n;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	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] <= n+1) DP[i] = max(DP[i+T[i]]+P[i], DP[i+1]);
		else DP[i] = DP[i+1];
	}

	cout << *max_element(DP, DP+n+1);
	return 0;
}