[Baekjoon] 15486번: 퇴사 2

🥅 문제

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

 

🔍 설계

데이터가 엄청 많고, 최대의 이익을 얻도록 상담을 구성하므로, 다이나믹 프로그래밍으로 방향을 잡았다.

 

dp[i]에는 상담을 i번째 날까지 했을 때, 최대 이익을 저장한다.

 

i로부터 상담이 끝나는 날은 i + 소요 날 - 1이고, 이것을 finish_day로 지정하였다.

 

i번째 날에 상담을 시작한다면, 상담이 끝난 날 얻는 이득인 dp[finish_day]는 dp[i-1] + 상담 이익이다. 여기서 dp[i]가 아닌 dp[i-1]을 더해야 함에 유의한다. dp[i]는 i번째 날까지 상담이 이루어지므로 상담을 시작할 수 없다.

 

또한, i번째 날에 상담이 끝나지 않는 경우를 고려하면, 전날까지의 이익과 비교하여 최댓값을 구하는 dp[i] = max(dp[i], dp[i - 1]); 를 추가해야 한다.

 

👊 풀이

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

int n, finish_day, result;
vector<pair<int, int>> info(1500001);
vector<int> dp(1500001);

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> info[i].first >> info[i].second;

		dp[i] = max(dp[i], dp[i - 1]);

		finish_day = i + info[i].first - 1;
		if (finish_day > n) {
			continue;
		}
		dp[finish_day] = max(dp[finish_day], dp[i - 1] + info[i].second);

;	}

	for (int i = 1; i <= n; i++) {
		result = max(result, dp[i]);
	}

	cout << result << "\n";
	return 0;
}