[BOJ] 14501 : 퇴사 (C++) with DP

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

14501번: 퇴사

걸린 시간 : 21분 33초

---

알고리즘

다이나믹 프로그래밍이다. 예시로 나온 걸 차례대로 다 해보고, 거기서 일반항을 도출하면 끝이다.

모든 요소들을 돌면서 cost라는 dp 배열에 다음과 같이 실행한다.

cost의 초기 상태는 모두 0이다.

1. i번째 요소는 현재 그 값이거나, 아니면 이전에 현재 값보다 더 큰 값이 올 수 있었다면 그 값이다. 따라서 최댓값을 하나 변수에 저장해두고 탐색할 때마다 i번째 요소를 최신화한다.
2. 만약 이 상담을 진행하면 N+1 째날에 퇴사할 수 없을 경우, 즉 인덱스를 벗어날 경우 고려하지 않는다.
3. 이번 상담을 했을 경우, 상담이 끝나는 날에 2가지 값 중 최댓값을 선택한다. 상담을 하는 경우 (cost[i] + P[i]) 혹은 상담을 하지 않는 경우 원래값 (cost[i] + T[i])
4. 모든 경우에서 가장 큰 값을 찾아 출력한다.

정답 코드

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

int N;
int cost[16], T[16], P[16];

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> T[i] >> P[i];
	int mx = 0;
	for (int i = 0; i <= N; i++) {
		cost[i] = max(mx, cost[i]);
		if (i + T[i] <= N) {
			cost[i + T[i]] = max(cost[i] + P[i], cost[i + T[i]]);
		}
		mx = max(mx, cost[i]);
	}
	int ans = 0;
	for (int i = 1; i <= N; i++) {
		ans = max(ans, cost[i]);
	}
	cout << ans;
	return 0;
}