[14501] 퇴사

---

https://www.acmicpc.net/problem/14501

14501번: 퇴사

Dynamic Programming 문제이다.

사실 잘 몰라서 구글의 힘을 빌렸다. 오랫동안 안하다보니 머리가 굳은 것 같다ㅠㅠ

 

A[i]를 i일에 받는 최대의 금액이라고 정의한다.

또한 받는 돈은 업무가 끝난 후 다음날에 들어온다고 가정한다.

 

1) i번째 날에 일한 경우

퇴사날을 넘기면 안되므로 조건문을 만든다. 

i+T[i]<=N+1이라면 퇴사날을 넘기는 것이 아니므로 ok!

 

2) i번째 날에 일하지 않은 경우

이는 간단하게 A[i+1]과 A[i]을 비교하여 더 큰 값을 넣는다.

 

#include <iostream>
#include <cmath>
using namespace std;

int N;
int T[17]; int P[17];
int A[17];
/*
	A[i] = i일까지 얻는 이익
*/
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> T[i] >> P[i];
	}

	// 그 다음날에 돈이 들어온다고 가정
	for (int i = 1; i <= N ; i++) {
		// i번째 날에 일 했을 경우
		if (i + T[i] <= N + 1) {
			// 퇴사 전 날까지만 일해야 함
			A[i + T[i]] = max(A[i + T[i]], A[i] + P[i]);
		}
				// i번째 날에 일을 하지 않았을 경우
		A[i + 1] = max(A[i + 1], A[i]);
	}

	cout << A[N + 1];
}