[BOJ14501][C++] 퇴사

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

14501번: 퇴사

문제

 

해결

처음에는 1일부터 시작해서 최대값 계산, 2일부터 시작해서 최대값 계산, ... 으로 생각했더니 i일에서 Ti일이 지난 후부터 -> 마지막 날까지 사이의 최대값을 계속해서 계산해야 하는 문제가 발생했다.

 

두번째는 i일에서 시작하여 Ti일 이후에 Pi를 더하고, 다시 T[i+Ti]일 이후에 P[i+Ti]를 더하여 누적하는 방식으로 했다. (마지막 테스트케이스를 돌려보기 전까지는 맞는 줄 알았음..)

-> T[i+Ti]일보다 이후의 날의 P값을 더했을 때 더 커지는 경우가 있었음 (마지막 테스트케이스)

 

🎈Key Point🎈

다이나믹 프로그래밍으로 문제를 해결한다. 

i일까지 받을 수 있는 최대 금액을 mx[i]에 저장한다. i는 0부터 N까지 돌면서 P[i]에 P[i+T[i]]를 더하는데 이 때, 원래 mx[i+T[i]]에 저장된 최대 금액과 새로 구한 최대 금액 중 더 큰 값으로 대체하여 저장한다. 그리고 하루 전 날까지 했을 때 받을 수 있는 최대 금액과 오늘까지 받을 수 있는 최대 금액 중 큰 값을 오늘까지 받을 수 있는 최대 금액으로 저장한다.

N일을 돌면 최종 값은 mx[N]에 저장되었을 것이므로 mx[N]값을 출력한다.

 

[전체 코드]

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

using namespace std;
typedef pair<int, int> pi;

int N;
vector<pi> v;
int mx[25];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back({ a, b });
	}
	///////////

	for (int i = 0; i < N; i++) {

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

	cout << mx[N];
}