[c++/백준] 14501 퇴사

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

14501번: 퇴사

세상에는 똑똑한 사람이 너무 많다..물론 내가 바보일지도?

 

처음부터 생각하느라 뇌정지왔는데 거꾸로 풀면 간단하게 풀린다.

 

 

 

ex) n=7, 아래와 같이  day와 cost가 주어질 때

 

맨 뒤부터 풀게되면 i=7일 때 date=7+2 이기 때문에 n보다 큰 수여서 dp가 0이 된다. 

i=6일 때도 date=6+4 이기 때문에 n보다 큰 수여서 dp가 0이 된다.

	1일	2일	3일	4일	5일	6일	7일
day	3	5	1	1	2	4	2
cost	10	20	10	20	15	40	200
dp						0	0

i=5일 때부터는 date가 n을 넘어가지 않기 때문에 비교할게 생긴다.

비교 대상은 이 전에 계산했던 (i=6일 때의 값 dp[6])과, (i=5일 때 값 + dp[7])일때의 더 큰 값을 적어주면 된다.

	1일	2일	3일	4일	5일	6일	7일
day	3	5	1	1	2	4	2
cost	10	20	10	20	15	40	200
dp					15	0	0

같은 방법으로 비교하다보면 이런 표가 만들어진다. 

이 표에서는 i가 6,7일 때만 date값이 n을 넘지만, date 값이 n을 넘으면 dp[i+1] 값으로 대체한다.

	1일	2일	3일	4일	5일	6일	7일
day	3	5	1	1	2	4	2
cost	10	20	10	20	15	40	200
dp	45	45	45	35	15	0	0

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

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

	int cost[20] = {};	//금액
	int day[20] = {};	//기간
	int dp[20] = {};

	int n;
	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> day[i];
		cin >> cost[i];
	}
	//거꾸로 생각하기
	for (int i = n; i >= 1; i--) {
		//현재 날짜 + 상담할 때 필요한 기간
		int date = i + day[i];

		//날짜가 안맞는 경우 (상담할 때 필요한 기간이 n을 초과할 때)
		if (date > n + 1) {
			dp[i] = dp[i + 1];	//날짜 초과되면 이 전에 계산한 금액으로 대체
		}
		else {
			//max(이 전에 계산한 금액, 현재 cost + 이미 저장되어있는 dp[date])
			dp[i] = max(dp[i + 1], dp[date] + cost[i]);
		}
	}
	cout << dp[1] << endl;
	return 0;
}

dp가 조금만 복잡해져도 뇌정지 옴,, 다양한 케이스의 dp를 분석하고 많이 접해봐야할듯.