[ 백준 15486 ] 퇴사 2 (C++)

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

15486번: 퇴사 2

 

다이나믹 프로그래밍 문제다. Dp는 먼저 점화식을 세운 뒤에 코드를 짜는게 편하다. 개인적으로 Dp 문제를 풀 때 Dp 값이 무엇을 뜻하는지 아는 게 정말 중요하다고 생각한다. 이 문제의 경우 dp[i]는 무엇을 뜻할까? 

 

dp[i] 란 i일동안 누적한 최대 이익을 말한다. 예를 들어 dp[13] = 64 이라면 13일까지의 최대 이익은 64라는 뜻이다. 

 

초기 dp 값들은 모두 0이다. dp값은 아래와 같은 점화식으로 갱신된다.

 

dp[today + day] = max(dp[today + day], dp[today] + point);

 

오늘(today)의 최대 이익에 day 만큼 일해서 얻을 수 있는 point와 (오늘 + day)의 최대 이익을 비교해서 큰 값을 dp[today + day]에 넣어주면 된다. 즉, 지금 일해서 얻을 수 있는 최대 이익이 미래보다 크면 이익을 더해주는 방식이다. 

 

 

추가로 오늘의 최대 이익이 내일의 최대이익보다 크면 내일의 최대이익에 오늘의 최대이익을 넣어준다. 말이 좀 길어서 그렇지 점화식으로 보면 간단하다. 점화식은 아래와 같다. 

 

dp[today + 1] = max(dp[today], dp[today + 1]);

 

이게 가능한 이유는 오늘까지 완료한 일은 내일이 돼도 그대로기 때문이다. 

 

#include <iostream>
#include <algorithm>
using namespace std;

int dp[1500001];  
int n, day, point; 

int main() {

	cin >> n;

	for (int today = 1; today <= n; today++) {
		cin >> day >> point;
		dp[today + day] = max(dp[today + day], dp[today] + point);
		dp[today + 1] = max(dp[today], dp[today + 1]);
	}

	cout << dp[n + 1] << endl;

	return 0;
}