알고리즘_퇴사(14501)

## 퇴사_14501

퇴사하기 전 상담기간 동안 가장 많은 가치를 얻기 위해 어떻게 상담을 해야 하는지에 대한 문제이다. 개인적으로 쉽다고 생각은 안했으나 실버 4...   
내가 풀었다는 거 자체가 실버 정도 레벨임이 맞는 것 같다. 문제를 푸는데 45분 정도의 시간이 걸렸다. DP 문제로 쉬운 난이도의 DP이다. 

    for (int i = 1; i <= n; i++) {
        max_value = 0;
        for (int j = 1; j <= i - 1; j++) {
            if (i - t[j] >= j) {
                max_value = max(d[j], max_value);
            }
        }
        if (i + (t[i] - 1) <= n)
            d[i] = max_value + p[i];
        else
            d[i] = 0;
    }

중간 반복문에서 i -t[j] >= j 라는 조건을 넣으면서 들어갈 수 있는 최대값을 찾아주었다.   
max_value를 찾고 dp 배열에 더해주는데 (i + t[i] <= n) 라는 조건으로 처음 했을 때 이상하게 되었다. 당일 상담이 끝나는 경우 t[i] 는 1이나 실제적으로는 0이 되야 함으로 t[i]에 -1을 해주었다. 

 

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	int n;
	int t[16]; // day
	int p[16]; // cost
	vector<int> d(16); //dp
	int max_value;
	int res;

	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> t[i] >> p[i];
	for (int i = 1; i <= n; i++) {
		max_value = 0;
		for (int j = 1; j <= i - 1; j++) {
			if (i - t[j] >= j) {
				max_value = max(d[j], max_value);
			}
		}`````````````````````````````
		if (i + (t[i] - 1) <= n)
			d[i] = max_value + p[i];
		else
			d[i] = 0;
	}
	res = *max_element(d.begin() + 1, d.begin() + n + 1);
	cout << res << "\n";
}