[C++] 백준 14501번 퇴사

 

1) 문제설명

백준 Online Judge 14501번 퇴사

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

14501번: 퇴사

 

2) 아이디어

DP문제를 1부터 차근차근 시도하다가 끝부분에서 Ti가 N을 넘어버리면 안 되기 때문에 구현에 어려움을 느꼈다.

또한 상담에 걸리는 일수에 따라 최댓값이 바뀌는 것에 대한 점화식도 생각해야 했다.

그래서 반대로 끝에서부터 차근차근 생각하였다.

문제에 있는 표를 끝에서 부터 살펴보면

DP [7] = 0 -> Ti 가 2기 때문에 범위(N)를 넘어가 버린다.

DP [6] = 0  -> Ti 가 4기 때문에 범위(N)를 넘어가 버린다.

DP [5] = 15 -> Ti가 범위를 넘어가지 않는다.

DP [4] = 20 + 15 -> Ti가 범위를 넘어가지 않고 4일의 Ti가 1이기 때문에 20을 더해준다.

DP [3] = 10 + 20 + 15 -> 3일의 Ti가 1이기 때문에 10을 더할 수 있다.

DP [2] = (20) OR (10 +20 +15) -> 2일의 Ti가 5이기 때문에 5일 동안 상담을 하지 못할 때 최댓값 vs 그전까지의 최대값

DP [2]에서 2일에 상담을 했을경우 5일동안 상담을 하지 못하기때문에 DP[2] = DP [2+5] + 20( 2일 차 상담 값 ) 이 성립한다.

즉 점화식은 DP [i+Ti] + Pi이고 최종적으로 DP [i] = MAX(DP [i+Ti] + Pi, i 날을 제외한 나머지의 최대 값) 이 된다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;
int t[1001];
int p[1001];
int dp[100001]; // 최대 이익
// 선택을했을떄 못고르는것을 어떻게 구현하느냐?

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> t[i] >> p[i];
	}
	// dp[7] = 0
	// dp[6] = 0
	// dp[5] = 15
	// dp[4] = 15 + 20
	// dp[3] = 15 + 20 + 10
	// dp[2] = 20 or 15 +20 +10
	// dp[1] = (10 + 20 + 15) or (15 + 20 + 10) or (20)
	for (int i = n; i >= 1; i--) {
		int temp = 0;
		for (int j = i; j <= n; j++) {
			if (i + t[i] - 1 > n) { // 기간을 넘기면 안된다.
				dp[i] = dp[i + 1];
			}
			else {
				if (dp[j] > temp) {
					temp = dp[j];
				}
				dp[i] = max(temp, dp[i + t[i]] + p[i]);
				//dp[1] = dp[1+3]+10 +
			}
			
		}
	}
	cout << dp[1];
}