[백준] 14501번. 퇴사 (C++)

문제 설명

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

14501번: 퇴사

 

해결 방법

 

dp문제 이다.

 

schedule[i][0] i번째 상담의 기간(T)

schedule[i][1] i번째 상담의 금액(P)

dp(21,0) N의 최댓값이 15이고 T의 최댓값이 5이므로. 

 

N-1번째 날 부터 0번째 날까지 거꾸로 확인했다.

if (i + schedule[i][0] > n) { dp[i] = dp[i + 1]; } 퇴사일을 넘어서 상담을 하지 못하는 경우
else
{
    acceptCase = dp[i + schedule[i][0]] + schedule[i][1]; 

    i번째 일을 수락할 경우 이익 = i번째 일이 끝난 후 하는 일의 금액 + i번째 일의 금액
    denyCase = dp[i + 1];

    i번째 일을 거절할 경우 이익 = i+1번째 일을 수락할 경우의 이익
    dp[i] = max(acceptCase, denyCase);

    둘 중 더 높은 금액을 선택
}

#include<iostream>
#include<vector>
using namespace std;
#define MAX 21

int main() 
{
	//INPUT==============================================
	int n; cin >> n;

	vector<vector<int>> schedule(n, (vector <int>(2)));
	vector<int> dp(MAX,0);
	
	for (int i = 0; i < n; i++)
	{	cin >> schedule[i][0] >> schedule[i][1];	}

	
	//SEARCH=============================================

	int acceptCase; //i번째 일을 수락했을 때 이익
	int denyCase; //i번째 일을 거부했을 때 이익

	for (int i = n-1; i >= 0; i--)
	{
		if (i + schedule[i][0] > n)
		{	dp[i] = dp[i + 1];	}
		else
		{
			acceptCase = dp[i + schedule[i][0]] + schedule[i][1];
			denyCase = dp[i + 1];
			dp[i] = max(acceptCase, denyCase);
		}
	}

	cout << dp[0];
}