[C/C++] 백준 14501번 - 퇴사

 

 

<코드>

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

int N, tmp;
int T[1001];
int P[1001];
int dp[1001];

int main()
{
	ios_base::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++)
	{
		tmp = 0;
		for (int j = 1; j <= i; j++)
		{
			int day = i - j + 1;

			if (day >= T[j])
			{
				tmp = max(tmp, P[j]);
			}
		}
		P[i + 1] += tmp;
		dp[i] = tmp;
	}
	cout << dp[N] << '\n';
}

 

풀이 방법

 

dp[i] : i일 까지 얻을 수 있는 최대 수익

 

날짜	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200
dp	0	0	10	30	30	45	45

1일차 상담이나 3일차 상담을 받게되면 3일에 10의 수익을 낼 수 있다. 이 수익을 다음날 상담에 누적시킨다고 생각해보면 4일차 상담이 끝나는 날에는 20 + 10 = 30의 수익을 낼 수 있다. 그리고 마침 4일차 상담 기간이 하루이기 때문에 4일차 최대 수익은 30이 된다.

4일차까지의 최대 수익을 다음날인 5일차에 누적시킨다면 15 + 30 = 45가 된다. 그러나 5일차 상담은 기간이 이틀이기 때문에 5일차 까지의 최대 수익은 30이 된다. 그리고 이 수익을 6일차에 누적시킨다. 

6일차 상담을 끝내게 된다면 30 + 40 = 70의 수익을 얻을 수 있지만 상담기간이 4일로, 퇴사이후에 상담이 끝나게 된다. 1일~6일사이에서 얻을 수 있는 최대 수익(dp)는 5일차 상담을 마치고 받게되는 45이며 이 수익을 7일차에 누적시킨다. 따라서 7일차 상담이 종료되면 수익은 200 + 45 = 245가 된다. 그러나 퇴사이후 상담이 끝나게 되므로 1~7일 사이의 최대 수익인 45가 정답이다.

 

<정답 출력 후 P의 변화>

날짜	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	30	45	70	245
dp	0	0	10	30	30	45	45

 

 

 

 

www.acmicpc.net/problem/14501

14501번: 퇴사