Zombie’s Treasure Chest

Some brave warriors come to a lost village. They are very lucky and find a lot of treasures and a big treasure chest, but with angry zombies.

The warriors are so brave that they decide to defeat the zombies and then bring all the treasures back. A brutal long-drawn-out battle lasts from morning to night and the warriors find the zombies are undead and invincible.

Of course, the treasures should not be left here. Unfortunately, the warriors cannot carry all the treasures by the treasure chest due to the limitation of the capacity of the chest. Indeed, there are only two types of treasures: emerald and sapphire. All of the emeralds are equal in size and value, and with infinite quantities. So are sapphires.

Being the priest of the warriors with the magic artifact: computer, and given the size of the chest, the value and size of each types of gem, you should compute the maximum value of treasures our warriors could bring back.

자… 저는 이 문제를 처음에 각 에메랄드, 사파이어에 대해서 두개 다 단위 가치를 계산했습니다. 그런 후에 효율 좋은 친구로 다 채워버리고 남은 공간에 남은 친구 넣을 수 있는 친구를 넣어서 결과를 냈거든용??

6
10 5 999 2 500
9 4 250 2 100
14 13 28 3 3
5 2 2 3 3
7 7 13 2 4
14 11 13 3 1

여기까지는 잘 되더라구요 그래서 딱 내봤더니? 터지구 펑펑펑!

그래서 정말 좀 더 뭘 해볼까 계속해서 고민해보다가 모르겠어서 이 로직 끝에 대충 for문 하나 넣어서 조합을 다 검사했거든용?

당연히 최악의 경우 2^31이라서 절대 불가능하죠…

그래서 좀 더 생각한게.. “범위를 어떻게 줄이지?” 였습니다. 이게 진짜 다행인게.. 다른 곳으로 빠졌으면 진짜 답이 없었거든용..

저는 일단 일단 원래 사용하던 방식을 조금 사용합니다. 그러면 기본적인 아이디어를 나열해 보겠습니다.

1. 일단 내가 선택하는 보석을 다 선택하면 남은 한 개의 보석을 최대한 많이 선택할거에요.(한 개의 보석을 다 얻었는데, 공간이 남았다.. 그러면 다른 보석을 넣을 수 있으면 무조건 최대한 많이 넣는다)
2. n > s1*s2이면 v1을 s2개 또는 v2를 s1개를 들고온다
   • n > s1 * s2이면 넣을 수 있는 공간이 두 보석의 크기를 곱한 것보다 크다는 의미이죠
   • 그래서 한 종류의 보석을 다른 보석의 크기만큼 채우는게 가능합니다
   • 예를 들자면, v1을 s2개 선택하면 s1 * s2 정도의 공간을 차지하고, 남은 공간은 s2로 최대한 채울 수 있습니다
   • 이렇게 되면 두 보석의 조합을 모두 고려해서 최적해를 보장합니다
3. 이제 다른 경우는 sqrt(N) 이하의 경우니까 요걸 bruteforce로 합니다
   • N ≤ s1*s2인 경우, s1과 s2 중 적어도 하나는 sqrt(N) 이하입니다
   • 그래서 공간을 적게 차지하는 보석을 기준으로 브포를 돌리면 최악이여도 sqrt(N) 정도로 해결 가능합니다

이 아이디어를 그냥 구현하면 됩니다. 아 그리고 구현을 좀 단순화하기 위해서 swap을 통해서 그냥 크기 정렬 해줬습니다

(아니 근데 이 문제 브포 테그 안 달려 있었다니까요?!?!??)

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

using ll = long long;
void swap(ll& a, ll& b){
    ll tmp;
    tmp = a;
    a = b;
    b = tmp;
}
ll solution(ll n, ll s1, ll v1, ll s2, ll v2) {
    ll result = 0;
    
    // cout << s1 << " " << s2 << "\n";
    if (s1 > s2) {
        swap(s1, s2);
        swap(v1, v2);
    }
    // cout << s1 << " " << s2 << "\n";
    if (s2 > sqrt(n)) {
        for (ll i = 0; i * s2 <= n; i++) result = max(result, (n - i * s2) / s1 * v1 + i * v2);
        return result;
    }
    if (v1 * s2 > v2 * s1) {
        swap(s1, s2);
        swap(v1, v2);
    }
    for (ll i = 0; i <= s2 && n - s1 * i >= 0; i++) result = max(result, (n - i * s1) / s2 * v2 + i * v1);
    
    return result;
}

int main() {
    int t;
    cin >> t;
    for (int i = 1; i <= t; ++i) {
        ll n, s1, v1, s2, v2;
        cin >> n >> s1 >> v1 >> s2 >> v2;
        cout << "Case #" << i << ": " << solution(n, s1, v1, s2, v2) << endl;
    }
    return 0;
}