※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
이 문제의 핵심은 기본 체력 100이 주어지고, 체력이 0 이하로 떨어지지 않으면서 얻을 수 있는 최대한의 행복을 구해야 합니다. 행복을 최대로 얻는다고 해서 행복의 크기로 정렬하여 큰 행복부터 얻게 하는 방법은 최적의 해답을 찾는데 사용할 수 없습니다. 왜냐하면, 하나의 행복의 크기는 더 작더라도, 잃는 체력에 대해 합산하면 더 큰 행복을 얻을 수 있는 경우가 존재하기 때문입니다. 따라서 인사를 하려는 인물 $now$와 현재 체력 $hp$에 대해 점화식은 다음과 같습니다.
$dp(now,hp) = max(dp(now+1,hp-lose[now]), dp(now+1,hp))$
이렇게 인사를 하는 경우와 안 하는 경우로 나누어 재귀함수를 실행하되, 인사를 하는 경우 체력이 0 이하로 떨어지는 경우가 없도록 해야하며, 다이나믹 프로그래밍 기법으로 문제를 해결하므로 반드시 결과를 memoization 해주셔야 합니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
#include<algorithm>
using namespace std;
int n, w[21][2], dp[21][101];
int dfs(int now, int hp)
{
if (now == n) return 0;
int &ret = dp[now][hp];
if (ret) return ret;
if (hp - w[now][0] > 0)
ret = dfs(now + 1, hp - w[now][0]) + w[now][1];
ret = max(ret, dfs(now + 1, hp));
return ret;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++) cin >> w[i][0];
for (int i = 0; i < n; i++) cin >> w[i][1];
cout << dfs(0, 100);
}