[백준 15486] 퇴사 2

문제 링크 => 15486번: 퇴사 2 (acmicpc.net)

15486번: 퇴사 2

---

Dynamic Programming 문제이다.

 

이 문제는 1일 2일 ... N일 접근을 해서 O(N) 만에 해결하도록 해야 한다.

 

문제에 주어진 Input을 기반으로 설명하고자 한다.

 

이때 dp[x] 는 x일 일때의 최대 이익을 의미한다.

 

x	T[x]	P[x]	dp[x]
1	3	10	0
2	5	20	0
3	1	10	0
4	1	20	0
5	2	15	0
6	4	40	0
7	2	200	0

 

여기서 차근차근 dp[x] 를 채워가도록 한다.

 

1일인 경우 ) 1 + T[1] = 4, 즉 4일이므로 4일에 금액 P[1] = 10을 벌 수 있다.

 

x	T[x]	P[x]	dp[x]
1	3	10	0
2	5	20	0
3	1	10	0
4	1	20	10
5	2	15	0
6	4	40	0
7	2	200	0

 

2일인 경우 ) 2 + T[2] = 7, 즉 7일이므로 7일에 금액 P[2] = 20을 벌 수 있다.

 

x	T[x]	P[x]	dp[x]
1	3	10	0
2	5	20	0
3	1	10	0
4	1	20	10
5	2	15	0
6	4	40	0
7	2	200	20

 

3일인 경우 ) 3 + T[3] = 4, 즉 4일이므로 4일에 금액 P[3] = 10을 벌 수 있다.

 

그러나, 이미 금액 10이 존재하므로 무시해도 무방하다.

 

x	T[x]	P[x]	dp[x]
1	3	10	0
2	5	20	0
3	1	10	0
4	1	20	10
5	2	15	0
6	4	40	0
7	2	200	20

 

4일인 경우 ) 4 + T[4] = 5, 즉 5일이므로 5일에 금액 dp[4] + P[4] = 30을 벌 수 있다.

 

x	T[x]	P[x]	dp[x]
1	3	10	0
2	5	20	0
3	1	10	0
4	1	20	10
5	2	15	30
6	4	40	0
7	2	200	20

 

5일인 경우 ) 5 + T[5] = 7, 즉 7일이므로 7일에 금액 dp[5] + P[5] = 45을 벌 수 있다.

 

그러나 기존에 있던 7일의 금액 20이 45보다 작으므로 최신화를 해줘야 한다.

 

즉, dp[5] + P[5] > dp[7] 이므로 dp[7] = dp[5] + P[5] = 45 로 변경한다.

 

x	T[x]	P[x]	dp[x]
1	3	10	0
2	5	20	0
3	1	10	0
4	1	20	10
5	2	15	30
6	4	40	0
7	2	200	45

 

6일인 경우 ) 6 + T[6] = 10, 8일을 넘어선 경우이므로 무시한다.

 

그러나 이전의 최대금액이 30이므로 이 값을 유지하기 위해 dp[6] = max(dp[5], dp[6]) = 30 을 채워준다.

 

 

x	T[x]	P[x]	dp[x]
1	3	10	0
2	5	20	0
3	1	10	0
4	1	20	10
5	2	15	30
6	4	40	30
7	2	200	45

 

7일인 경우 ) 7 + T[7] = 9, 9일을 넘어선 경우이므로 무시한다.

 

그러나 이전의 최대금액이 30인데 현재 7일의 금액이 45이므로 무시한다.

 

x	T[x]	P[x]	dp[x]
1	3	10	0
2	5	20	0
3	1	10	0
4	1	20	10
5	2	15	30
6	4	40	30
7	2	200	45

 

따라서 최종 최대 금액은 45이다.

 

(0) dp[i] = max(dp[i], dp[i - 1]) 을 해줘서 이전의 (i - 1) 일의 최대 금액을 유지시키는게 핵심이다.

 

(1) 여기서 주어진 날짜를 만족하는 경우는 x + T[x] <= N + 1 을 만족해야 한다. (N은 input값)

 

(2) (1)을 만족하는 경우 dp[i + T[i]] = max(dp[i + T[i]], dp[i] + P[i]) 를 구해준다.

 

이렇게 i 값을 1부터 N까지 완료하고 마지막으로 max(dp[N], dp[N + 1]) 을 출력해주면 된다.

 

왜냐면 N 일이 퇴사일이 아니므로 (N + 1)일 까지 채워진 값까지 고려하는것 또한 핵심이다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <string.h>
#include <cstring>
#include <queue>
#include <stack>
#define endl '\n'
#define INF 1000000000
#define ll long long

using namespace std;

int N, T[1500001], P[1500001], dp[1500001];

void input() {
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> T[i] >> P[i];
}

void solution() 
{
	for (int i = 1; i <= N; i++) {
		dp[i] = max(dp[i], dp[i - 1]);
		if (i + T[i] <= N + 1) {
			dp[i + T[i]] = max(dp[i + T[i]], dp[i] + P[i]);
		}
	}

	cout << max(dp[N], dp[N + 1]) << endl;
}

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

	input();
	solution();

	return 0;
}