[백준 14501] 퇴사

얼핏보면 배낭 0-1문제랑 정말 비슷해보이는데

제약조건이 있어 점화식이 달라진다

 

배낭문제는 담을 수 있으면 언제나 특정 물건을 담을 수 있었다

하지만 이 문제는 특정 상담을 할 수 있는 경우가 하루에 그친다

왜냐하면 한 개의 상담은 오직 해당 날짜에만 할 수 있기 때문이다

그 점을 생각해서 점화식을 짜면 아래와 같이 나옴

 

DP 논리는 평범한 배낭과 동일하다

내려가면서 특정 상담을 1개씩 더 고려한 결과가 나오는 것이다

 

---

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

#define SIZE 16

using namespace std;

int N;
int dp[SIZE][1001] = { 0, };
int W[SIZE], V[SIZE];

void solve() {
	for (int i = 1; i <= N; i++) {
		for (int k = i; k <= N; k++) {
			// i번째 상담을 고려할 수 있는 경우면
			if (k - W[i] + 1 == i) {
				dp[i][k] = max(dp[i - 1][k], dp[i - 1][k - W[i]] + V[i]);
			}
			else {
				dp[i][k] = max(dp[i - 1][k], dp[i][k - 1]);
			}
		}
	}
}

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

	cin >> N;

	for (int i = 1; i <= N; i++) {
		cin >> W[i] >> V[i];
	}

	solve();

	cout << dp[N][N];

	return 0;
}