[백준 14501] 퇴사 (C++) - S3

문제

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

14501번: 퇴사

 

개요

문제를 다 읽자마자 DP로 접근해야겠다는 생각이 들었다.

그래서 dp[i]를 'i번째 날까지의 최대 금액'으로 정한 후에, 점화식을 계속 생각해보았는데, 20분 넘게 떠올리지 못했다.

이차원 dp 배열을 이용한 접근도 시도했는데, 파고들수록 더 복잡해질 것 같았다.

그래서 결국 구글링한 후에 블로그 글을 참고하여 풀었다.

 

문제 풀이

이 문제의 핵심은 앞에서부터 생각하는 것이 아니라, 뒤에서부터 생각하는 것이다.

 

	1일	2일	3일	4일	5일	6일	7일
t[i]	3	5	1	1	2	4	2
p[i]	10	20	10	20	15	40	200
dp[i]

 

만약 앞에서부터 생각한다고 해보자.

만약 1일차에 상담을 시작하게 된다면, t[i] = 3이므로 1일, 2일, 3일에 상담을 진행한다.

만약 2일차에 상담을 시작하게 된다면, t[2] = 5이므로 2일, 3일, 4일, 5일, 6일에 상담을 진행한다.

만약 3일차에 상담을 시작하게 된다면, t[3] = 1이므로 3일에만 상담을 진행한다.

 

앞에서부터 시작한 경우에, 3일차의 상담이 위의 3번의 경우에 모두 겹치는 상황이다.

그러면 이 3일차는 어느 경우에 포함되는 것이 가장 이득인지 알아내기 어렵다.

 

그러나, 만약에 뒤에서부터 시작한다면?

7일차부터 순서대로 4일차까지, 즉 4일차에 상담을 시작한 경우의 최대 금액을 구한 상태이다.

이 때, 3일차를 고려하는 경우는 단순한다.

3일차에 상담을 진행하는 경우 or 3일차에 상담을 진행하지 않는 경우 2가지만 고려하면 된다.

 

3일차에 상담을 진행하는게 이득일지, 진행하지 않는 게 이득일지는 두 가지의 값을 비교해야 한다.

 

1) 3일차에 상담을 진행했을 때가 더 최대 수익인 경우

→ 3일차에 상담을 진행했을 때의 가격(p[i])과, 3일차에 시작한 상담이 t[3]만큼의 시간이 걸려 완료된 후에 3 + t[3] = next 시점에 상담을 시작했을 때의 최대 가격(dp[next])의 합, 즉 p[i] + dp[next]

 

2) 3일차에는 상담을 진행하지 않고, 4일차에 상담을 진행했을 때가 더 최대 수익인 경우

→ 4일차에 상담을 시작했을 때의 최대 가격, 즉 dp[i + 1]

 

따라서, dp[i]는 dp[i + 1]과 p[i] + dp[next] 중에서 더 큰 값이 된다.

→ dp[i] = max(dp[i + 1], p[i] + dp[next])

 

	1일	2일	3일	4일	5일	6일	7일
t[i]	3	5	1	1	2	4	2
p[i]	10	20	10	20	15	40	200
dp[i]

 

코드

#include <iostream>
#include <cstring>
#include <sstream>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <algorithm>
#include <bitset>
#include <cmath>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n; cin >> n;
	vector <int> t(n + 2); // 걸리는 기간
	vector <int> p(n + 2); // 금액
	vector <int> dp(n + 2); // i번째 날부터 고려 시 최대 금액
	for (int i = 1; i <= n; i++) {
		cin >> t[i] >> p[i];
	}
	for (int i = n; i > 0; i--) {
		int next = i + t[i];
		if (next > n + 1) { // i일차에 상담 시작했는데, 완료 기간이 n일차를 넘는 경우
			dp[i] = dp[i + 1]; // i일차에는 상담 진행X, (i + 1)일차의 최대 금액 그대로 가져옴
		}
		else {
			dp[i] = max(dp[i + 1], p[i] + dp[next]);
		}
	}
	cout << dp[1];
	return 0;
}

 

깨달은 점

DP 문제는 'DP로 풀면 되겠다!'라고 생각이 드는 것까지는 쉬운데, 정확한 점화식을 찾는 과정이 항상 어렵다.

이 문제와 같이 뒤에서부터 DP 점화식을 찾는 방식의 문제는 더더욱 어렵다.

DP 문제를 많이 풀면서 다양한 점화식을 접해보는 것이 중요할 것 같다.