[C++]백준 15486번: 퇴사 2

문제 출처

풀이

i일 금액을 결정하는 데에는 두 가지 선택권이 있다.

1. i-1일의 것을 선택한다.
2. i일 이전에 i일까지 딱 마감된 금액을 선택한다.

2가 무슨 말이냐면 예를 들어 1일차에 T1 = 3이고 P1 = 10이면 4일차에 금액이 0이 아닌 10부터 시작하는 것이다. 그리고 T2 = 2이고 P2 = 20이면 이미 4일차에 10이 있었지만 10과 15를 비교하고 이때 15가 더 크므로 P4가 15부터 시작하는 것이다. 그리고 나중에 4일차의 금액을 P3와 비교할 때 P3보다 P4가 더 크면 P4를 택하고 P3가 더 크면 P4는 P3의 금액을 따라간다. 다음은 전체 코드이다.

#include<iostream>
#include<vector>

using namespace std;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
	int N;
	cin >> N;
	vector<int> T(N + 1);
	vector<int> P(N + 1);
	vector<int> res(N + 2, 0);
	for ( int i = 1; i < N + 1; i++ ) {
		cin >> T[i] >> P[i];
	}
    
	for ( int i = 1; i < N + 1; i++ ) {		
		res[i] = max(res[i - 1], res[i]);	//직전일과 해당일을 비교
		if ( i + T[i] >= N + 2 )continue;	//날짜가 오바되는 경우
		res[i + T[i]] = max(res[i+T[i]],res[i] + P[i]); 
        /*이미 있었던 값과(res[i+T[i]])
          새로 들어갈 값(res[i]+ P[i])를 비교하여 큰 값을 넣는다.
        
        */
	}
	res[N + 1] = max(res[N], res[N + 1]);	
	cout << res[N + 1] << endl;

	return 0;
}