BOJ 14501: 퇴사

#BOJ 14501: 퇴사

14501번: 퇴사

#풀이

문제를 보고 생각 한 것은 일단 상담일을 시작한 날과 끝나는 날이 중요하다고 생각했다.

d 배열은 날까지 가장 많은 돈을 번 날이다.

 

그래서 i 번째 날 상담을 시작하면 i+t[i] -1 까지 일을 못하기 때문에 d[i+t[i]]을 구할 수 있다.

 

#코드

#include<iostream> //#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int n;
int t[20];
int p[20];
int d[20];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> t[i] >> p[i];
	}

	for (int i = 1; i <= n; i++) {
		d[i] = max(d[i], d[i - 1]);

		if (i + t[i] - 1 <= n)
		{
			d[i + t[i]] = max(d[i + t[i]], d[i] + p[i]);
		}
	}
	cout << max(d[n], d[n + 1]);
	return 0;
}