BOJ - 퇴사2 (15486)

0. 문제

문제 링크

1. 풀이

N의 크기가 최대 1,500,000이다. 따라서 일일히 선형 탐색($O(N^2)$)을 이용해 답을 찾으려 하면 TLE가 나게 된다.

시간복잡도의 문제를 다이나믹 프로그래밍으로 해결할 수 있으므로 다이나믹 프로그래밍을 이용한다.

처음 문제를 풀면서 잘못 생각해 실수한 부분이 있었는데, T의 최대가 50이라고 주어져 있으므로 $i$일차의 최대 수익은 그 앞의 50일동안의 최대 수익에 $i$일차 수익이라고 생각하였다.

그러나 이는 50일보다 더 이전에 진행한 상담을 고려하지 못한다는 오류가 존재함을 깨달아, 앞의 수익들 중의 최댓값을 저장해 가는 방식이 아닌 T와 무관하게 가장 마지막 수익으로부터 앞으로 진행하는 Top-down방식으로 구해나갔다.

마지막 날부터 첫째 날까지 역순회하며 $i$번째 날의 최대 수익을 찾는데, 만약 다음과 같은 경우

• $i$번째 날의 상담을 진행하면 퇴사일을 넘겨서 끝나는 경우
• $i$번째 날의 상담을 진행하지 않는 것이 더 높은 수익을 얻는 경우

$i$번째 날의 상담을 진행하지 않고, 이는 $memo[i] = memo[i+1]$이 된다.

그렇지 않다면 상담을 진행하는 것과 그렇지 않은 방법 중 더 높은 수익을 선택한다.

이후 전체 $memo$배열에서 가장 큰 값을 찾아 출력하면 이 값이 최대 수익이 된다.

2. 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

constexpr int MAXN = 1'500'001;
constexpr int MAXT = 50;

int arr[MAXN][2];
int memo[MAXN];
int n;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//freopen("input.txt", "r", stdin);

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i][0] >> arr[i][1];
	}
	
	for (int i = n; i >= 0; i--)
	{
		memo[i] = memo[i + 1];
		if (i + arr[i][0] <= n)
		{
			memo[i] = max(memo[i + arr[i][0]] + arr[i][1], memo[i]);
		}
	}
	cout << *max_element(memo, memo + n);
	
	return 0;
}

3. 결과