[백준 C++] 14501 : 퇴사

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

14501번: 퇴사

 

다이나믹 프로그래밍 (DP)와 브루트포스 알고리즘을 활용한 문제이다.

주어진 기간 안에 최대한의 이득을 확인하는 문제이기 때문에 점화식으로 계산하여, DP리스트에 그 날에 할 수 있는 최댓값을 넣어주면서 진행하면 된다.

N날이 되었을 때 DP[N]에 있는 값이 그 기간 안에 할 수 있는 최대의 가치를 가진 일이 될 것이다.

 

#include <iostream>

using namespace std;

int N;
int list[15][2];
int dp[15];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N;

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

	for (int i = 0; i < N; i++)
	{
		if (i + list[i][0] <= N)
			dp[i + list[i][0]] = max(dp[i + list[i][0]], dp[i] + list[i][1]);

		dp[i + 1] = max(dp[i + 1], dp[i]);
	}

	cout << dp[N] << endl;
}

dp값을 넣어줄 때, 현재 날짜와 그 상담을 진행하는 날짜를 더한 값이 N값보다 적을 경우 현재 i의 날짜에 들어있는 값과 그 상담의 금액을 합과 상담이 끝나는 날짜에 들어있는 최댓값을 비교해서 끝나는 날짜에 넣어준다.

다만, 그 날에 상담을 하지 않고 넘어가는 경우도 있기 때문에 그것과는 별개로 현재날과 그 다음날의 최대값을 비교해서 다음날에 값도 추가해주어 빈 공간이 존재하지 않게 만들어준다.