[알고리즘] C++ 백준 15486 퇴사2

 

백준 15486

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

15486번: 퇴사 2

풀이 전 나의 생각

본래 퇴사1 문제는 경우의 수가 적어서 DFS로 풀이가 가능했다.

하지만 퇴사2에서는 무려 N이 1500001까지 가능하기 때문에 무조건 DP로 풀어야한다.

 

이 문제의 포인트는 특정 날짜까지 최대 얼마를 벌 수 있는지 처음부터 탐색하는 것이다.

문제에서 나온 첫 예시를 기준으로 진행하면

 

1일까지 버는 돈이 없으니 0원

2일까지 버는 돈이 없으니 0원

3일까지 버는 돈이 없으니 0원

4일까지 일해서 버는 돈의 경우는 1일에서 3일동안 일한 경우와 3일에서 1일동안 일한 경우, 둘다 10이니 4일 까지 일해서 벌 수 있는 돈은 10

그럼 5일까지 일을해서 벌 수 있는 돈의 경우의 수는 4일까지 번 돈 + 4일째 일한 돈 과  5일까지 벌을 수 있는 최대의 돈

하지만 아직 5일까지 일해서 벌을 수 있는 최대의 돈은 구해져 있지 않아 10 + 20을 한 30이 5일 까지 벌을 수 있는 최대의 돈이 된다.

 

그럼 이를 식으로 나타내면

N일은 DP[N + N의 기간] = max(현재까지 얻을 수 있는 최대값 + N의 현재 금액,  N + N의 기간까지 얻을 수 있는 최대 금액)

 

예를 들어 1일에서 3일동안 일하면 10원을 얻으니 4일까지 일해서 벌을 수 있는 돈은 10원이다. => DP[4] = 10

2일에서 5일동안 일하면 20원을 얻으니 => DP[7] = 20

3일에서 1일동안 일하면 10원을 얻으니 => DP[4] = 10

그럼 여기서 알 수 있는건 DP[4] 이전까지인 1 ~ 3은 돈을 벌 수 있는 경우가 없다는 것이다.

그러니 DP[4]에서 현재 벌 수 있는 최대금액이 갱신된다.

그러니 현재 벌 수 있는 최대금액 + 내가 N날짜에 벌 수 있는 최대금액 과 현재N + N의 기간까지 벌 수 있는 최대값을 비교해야 한다.

더 자세히 설명하자면 

 

day1. 3일 100원

day2. 1일 120원

day3. 2일 20원

day4. 2일 10원

 

이렇게 있다고 가정하면 day1은 dp[4] = 100이 나오고  day2에서 dp[3] = 120이 될 것이다.

day3까지 벌 수 있는 최대금액이 120으로 갱신된 상태고 day4에서는 DP[6]를 구해야 할 차례다.

그럼 경우의 수는 day1 - day 4 과 day2 - day4로 나뉘기 때문에 아까 갱신된 최대금액 120원이 올바른 분기를 

바라보게 해준다. 그러니 N까지 벌 수 있는 최대금액을 계속 갱신 시키면서 N+1까지 탐색을 진행하여 N + 1일 까지 벌 수 있는 돈을 구하면 최종 결과값을 얻을 수 있다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>

using namespace std;
int dp[1500001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	vector<pair<int, int>> day;
	int n, res = 0;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int t, p;
		cin >> t >> p;

		day.push_back({t, p});
	}
	day.push_back({0, 0});

	for (int i = 1; i <= n + 1; i++)
	{
		res = max(res, dp[i]);
		if (i + day[i - 1].first <= n + 1 )
		{		
			dp[i + day[i - 1].first] = max(dp[i + day[i - 1].first], res + day[i - 1].second);
		}
	}
	cout << res;
}