안녕


작성일 : 2017-01-11 01:21:41
조회수 : 376



설명

※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


이 문제의 핵심은 기본 체력 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);
}

안녕 - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글