[BOJ] 백준 15486 퇴사 2 c++ (DP)

문제 출처 : https://www.acmicpc.net/problem/15486

15486번: 퇴사 2

풀이

DP로 해결하는 문제이다.

뒤에서부터 탐색하는 방식으로 해결하였으며 앞에서부터 탐색하는 방법도 있다. 

---

dp[i]를 i일부터 시작했을때의 최댓값 이라고 하였다.

dp는 동적할당을 해주고 문제의 Ti와 Pi는 vector에 넣어주었다.

※ 1차원 배열 동적할당에서, new int[N]뒤에 ()을 붙이면 0으로 초기화 해준다.

	int *dp = new int[N + 2](); // ()붙이면 0으로 초기화
	vector<pair<int, int>> v(N + 2);

 

문제의 예제를 살펴보자.

dp[7]은 7일부터 시작했을때의 최댓값이다.

7일차 상담은 2일이 걸리므로 퇴사일을 초과하게 된다. 따라서 7일차의 최댓값은 0이다.

6일차 역시 초과하므로 dp[6]은 이전 dp의 최댓값(dp[6+1])일 것이다. (dp[6] = dp[7] = 0)

 

따라서 점화식은 다음과 같다.

if(v[i].first > N - i + 1) dp[i] = dp[i + 1];

앞서 dp배열과 vector를 N+2로 할당해준 것이 위의 dp[i] = dp[i+1]에서 i = N일경우 dp[N+1]을 참조하기 때문이다.

 

그렇다면 5일차를 확인해보자! 5일차의 경우 상담을 해도 퇴사 전에 상담을 끝낼 수 있다.

따라서 dp[5]는 P5(5일차 금액) + dp[5 + T5(5일차 기간)] (상담이 끝난 후 7일이므로 7일차의 최댓값) 와

5일차에 상담을 하지 않은 경우인 dp[6]을 비교한 최댓값이 된다.

dp[5] = max(15 + dp[5+2], dp[6]) = 15 가 되는 것이다.

 

이 역시 점화식으로 나타내면 다음과 같다.

dp[i] = max(dp[i + 1], v[i].second + dp[i + v[i].first]);

---

코드

dp[1]까지의 방법의 수를 미리 계산한 후 출력하였다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){	
	ios::sync_with_stdio(false); cin.tie(NULL);

	int N;
	cin >> N;

	int *dp = new int[N + 2](); // dp[i] i일부터의 최댓값

	vector<pair<int, int>> v(N + 2);

	for(int i = 1; i <= N; i++)
		cin >> v[i].first >> v[i].second;	

	for(int i = N; i >= 1; i--){
		if(v[i].first > N - i + 1) dp[i] = dp[i + 1];
		else dp[i] = max(dp[i + 1], v[i].second + dp[i + v[i].first]);		
	}

	cout << dp[1];

	return 0;
}

---

다른 방법

앞에서부터 계산하는 풀이도 있었는데 방법이 매우 좋아서 공유하려 한다.

i일에 상담을 하는 경우 / 안하는 경우 로 나누어서 해결하였는데

 

상담을 하는 경우 그 다음 상담은 i + T[i]가 되고 값은 dp[i] + p[i] 가 된다.

하지 않는 경우는 다음날인 dp[i+1] 이고 값은 그대로 dp[i]가 된다.

 

구하려는 값은 마지막날에 상담을 안하는 경우인 dp[i+1]로 계산해주면 된다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int dp[1500000 + 51];
int T[1500000 + 1];
int P[1500000 + 1];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    
    int n; 
    cin >> n;
    
    for (int i = 1; i <= n; i++)
        cin >> T[i] >> P[i];
    
    for (int i = 1; i <= n; i++) {       
        dp[i + T[i]] = max(dp[i + T[i]], dp[i] + P[i]);
        dp[i + 1] = max(dp[i + 1], dp[i]);
    }
 
    cout << dp[n + 1] << '\n';
}