[Algorithm]Baekjoon 29756번 :: DDR 체력 관리

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
#include <cmath>
 
using namespace std;
 
 
int n, k;
int scores[1003] = { 0 };
int damages[1003] = { 0 };
int dp[1003][103] = { 0 };
 
 
int DFS(int index, int curHP)
{
    if (index == n + 1) return 0;
 
    int& result = dp[index][curHP];
    if (result != -1) return result;
 
    result = 0;
 
    int newHP = min(100, curHP + k);
 
    // 포기
    result = DFS(index + 1, newHP);
 
    //  플레이
    if (newHP - damages[index + 1]  >= 0)
    {
        result = max(result, DFS(index + 1, newHP - damages[index + 1]) + scores[index + 1]);
    }
 
    return result;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> k;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> scores[i];
    }
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> damages[i];
    }
 
    memset(dp, -1, sizeof(dp));
    cout << DFS(0, 100);
}
 
 

 

나는 그냥 문제 그대로 Top-Down으로 풀었는데, 배낭문제에서 약간 변형됐다고 봐도 된다.

체력이 회복된다는 점 말고는, 조건에 따라 특정 노드를 집거나, 안집거나 하는 과정을 거쳐 최대값을 구하는거라서 배낭문제랑 비슷하다.