26595 전투의 신

나는 가성비를 따져서 탱커가 가성비가 높은지 / 딜러가 가성비가 높은지 나눠서

가성비가 높은 걸 최대한 담고 남은 걸 또 담으려고 했다

 

틀렸다ㅋㅋ

 

알고보니 냅색 개념이었다

 

15원이 있는데 딜러는 (13, 10) 탱커는 (7, 6)이라고 하면

13/10 = 1.3, 7/6 = 1.1

딜러가 가성비가 높아서 딜러 하나를 담는다. 

그런데 이런 경우는 탱커 둘 담는게 이득이다. 

 

O(1)에 푸는 건 불가능하고 결국 모든 경우 다 구하는 수 밖에 없다

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>
#include<cassert>
#include <climits>
#include <tuple>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MAXV 987654321
#define FOR(i, n) for(int i = 0; i < (n); ++i)

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int main() {
    i64 n;
    scanf("%lld", &n);
    
    i64 a, pa, b, pb;
    scanf("%lld %lld %lld %lld", &a, &pa, &b, &pb);
    
    i64 ans_a = 0;
    i64 ans_b = 0;
    i64 maxv = 0;
    // 딜러를 0명부터 .. 최대 수까지 구함
    for (i64 cnt_a = 0; (cnt_a * pa) <= n; cnt_a++) {
        // 그때 탱커 수도 구함
        i64 cnt_b = (n - cnt_a * pa) / pb;
        
        i64 power = a*cnt_a + b*cnt_b;
        if (maxv < power && (cnt_a * pa + cnt_b * pb) <= n) {
            maxv = power;
            ans_a = cnt_a;
            ans_b = cnt_b;
        }
    }
    
    printf("%lld %lld\n", ans_a, ans_b);
    
	return 0;
}