백준 BOJ 15486 - 퇴사 2

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

15486번: 퇴사 2

DP 사용해서 해결했다.

dp[i] 를 i일째 시점에서 상담을 끝냈을 때의 최대 이익으로 정의한다.

 

i일째에 상담을 진행한 경우는

dp[i+T[i]] 를 dp[i] + P[i] 로 갱신 할 수 있으며,

이때 편의상 T[i]와 P[i] 를 0부터 시작하는 인덱스로 관리해주면 소스코드가 깔끔해진다.

 

상담을 진행하지 않더라도,

지난 일자에서의 최대 수익을 그대로 가져와서 갱신해주면 되는데,

이때 비교해서 "갱신" 하는것이 아닌 단순히 "설정" 하면 안되는것이

앞선 dp[i+T[i]] 갱신 때문에 미리 0이 아닌 값이 들어가 있을 수 있기 때문이다.

 

이렇게 dp를 작성해주면 dp 배열의 정의에 따라 정답은 dp[N] 이 된다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll T[2000000] = {0};
ll P[2000000] = {0};
int N;

ll dp[2000000] = {0};

int main(){
	cin.sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N;
	for(int i=0; i<N; i++) cin >> T[i] >> P[i];
	
	for(int i=0; i<=N; i++){
		if(i)   dp[i] = max(dp[i], dp[i-1]);
		if(i<N) dp[i+T[i]] = max(dp[i+T[i]], dp[i] + P[i]);
	}
	
	cout << dp[N];
	return 0;
}