[Algorithm]Baekjoon 29792번 :: 규칙적인 보스돌이

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

29792번: 규칙적인 보스돌이

struct Node
{
    long long hp;
    long long money;
};
 
bool cmp(const Node& a, const Node& b)
{
    return a.hp > b.hp;
}
 
long long n, m, k, input1, input2;
vector<long long> damages;
vector<Node> bosses;
long long bossesHP[13] = { 0 };
long long bossesMoney[13] = { 0 };
 
long long DFS(int index, long long damage, long double second, long long sumMoney)
{
    long long answer = sumMoney;
 
    for (int i = index+1; i < k; ++i)
    {
        long double attackSecond = ceill(bosses[i].hp / (long double)damage);
        long long tempDamage = attackSecond * damage;
 
        if (second >= attackSecond && bosses[i].hp <= tempDamage)
        {
            sumMoney += bosses[i].money;
            answer = max(answer,DFS(i,damage, second - attackSecond, sumMoney));
            sumMoney -= bosses[i].money;
        }
    }
 
    return answer;
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m >> k;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> input1;
        damages.push_back(input1);
    }
 
    sort(damages.rbegin(), damages.rend());
 
    for (int i = 0; i < k; ++i)
    {
        cin >> bossesHP[i] >> bossesMoney[i];
        bosses.push_back({ bossesHP[i], bossesMoney[i] });
    }
 
    sort(bosses.begin(), bosses.end(), cmp);
    long long sumAnswer = 0;
 
    for (int i = 0; i < m; ++i) // 캐릭터들
    {
        sumAnswer += DFS(-1, damages[i], 900, 0);
    }
 
    cout << sumAnswer;
}

DP풀이 연습을 해야해서 배낭문제 풀이랑 매칭시키면서 풀어보려했는데 잘 안풀려서.. 일단 완전탐색으로 풀었다.

값들이 크기 때문에 long long과 long double을 이용해야 한다.