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

 

N+1일 퇴사하기 전에 백준이가 얻을 수 있는 최대 이익을 출력하는 문제이다.

익일을 기준으로 살펴보자.

 

만약 2일에 퇴사한다고 가정하자 그럼 1일에 있는 일은 3일이 소요되기 때문에 수행하지 못한다.

만약 3일에 퇴사한다고 가정하자  그럼 1일에 있는 일은 3일이 소요되고 2일에 있는 일은 5일이 소요되기 때문에 아무런 일도 못한다.

만약 4일에 퇴사한다고 가정하자 그럼 1일에 있는 일은 3일이 소요되기 때문에 (1일, 2일, 3일) 일하면 수행이 가능하다.

2일에 있는 일은 5일이 소요되기 때문에 수행이 불가능하다. 3일에 있는 일은 1일이 소요되기 때문에 수행이 가능하다.

(4일에 퇴사한다고 가정하면 1일에 있는 일을 하거나 3일에 있는 일을 하고 퇴사하면 된다.)

만약 5일에 퇴사한다고 가정하자 일이 가능한 요일은 1,3,4일이다. (4일은 이미 이전에 1일 or 3일의 금액을 더한 값이라서 큼) 최댓값을 5일에 넣으면 된다.

이런 느낌으로 N+1일까지 살펴보면 된다.

 

 

#include <iostream>

using namespace std;

int arr[16][2];
int DP[16];

int main(void)
{
	int N=0;
	cin>>N;
	
	for(int i=1; i<=N; i++)
	{
		cin>>arr[i][0];
		cin>>arr[i][1];
	}
	
	for(int i=1; i<=N+1; i++)
	{
		for(int j=1; j<i; j++)
		{
			if(i>=arr[j][0]+j)
			{
				if(DP[i]<DP[j]+arr[j][1])
				{
					DP[i]=DP[j]+arr[j][1];
				}
			}
		}
	}
	
	cout<<DP[N+1];
	
	return 0;
}