• 문제

    1

  • 고민

    d[i]를 i일차에 얻을 수 있는 최대 수익이라 생각해보았다. i일차에 상담을 했을 경우 t[i]일 이후에 i일차에 상담해서 번 수익을 기대할 수 있다. 그렇다면 i + t[i]에 i일차 상담을 했을 경우와 이전의 상담 내역때문에 상담하지 못했을 경우 중 최대 수익을 d[i + t[i]]에 넣는다. 이전에 상담하지 않았어도 i일차 이후에 상담하는 경우가 더 큰 수익을 얻을 수 있으므로 i + 1일차에 i일차에 상담하지 않았을 경우의 수익과 i + 1일차에 수익 중 큰 값을 d[i + 1]에 넣는다. d[n+1]에는 n일차까지 상담한 최대 수익이 계산되어 있을 것이다. d가 16 + 5인 이유는 n이 최대 15이고, t가 최대 5이므로 d[i + t[i]]의 최대 범위를 계산하기 위해 설정하였다.

  • 코드

    #include <iostream>
#include <algorithm>
using namespace std;
  
int t[16];
int p[16];
int d[16 + 5];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> t[i] >> p[i];
	}
	for (int i = 1; i <= n; i++) {
		d[i + t[i]] = max(d[i + t[i]], d[i] + p[i]);
		d[i + 1] = max(d[i + 1], d[i]);
	}
	cout << d[n + 1] << '\n';
	return 0;
}