[BOJ] 18712 Ice-cream Knapsack

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

---

문제

There is a wonderful ice-cream shop that contains N ice-creams, such that each ice-cream is represented by two numbers Ci and Hi denoting the number of calories and the happiness value, respectively.

You want to buy exactly K ice-creams such that the calories of the densest ice-cream (the one with most calories) are as minimal as possible. If there is more than one way to do that, you want to maximize the total happiness of the ice-creams you will buy, that is the sum of the happiness values of the chosen ice-creams.

---

실수 1. 문제에 대한 잘못된 이해

실수 2. 출력

 

1번에 대해서,

위 문제는 Ci 값을 기준으로 정렬 후 k번째 Ci의 값을 확인한 뒤,

같은 Ci값을 가지는 원소의 최대 인덱스를 확인해서 Hi에 대해 재정렬을 해야합니다

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct ch {
    ll c;
    ll h;

    bool operator < (const ch _ch) const{
        if(c != _ch.c) return c < _ch.c;
        return h > _ch.h;
    }
};

void solve(){
    int tc; cin >> tc;
    while(tc--){
        int n, k; cin >> n >> k;

        vector<ll> cs(n); for(auto &c:cs) cin >> c;
        vector<ll> hs(n); for(auto &h:hs) cin >> h;
        vector<ch> chs(n);
        for(int i=0; i<n; i++) chs[i] = {cs[i], hs[i]};
        stable_sort(chs.begin(), chs.end());

        ll max_c = 0, sum_h = 0;
        for(auto el:vector<ch>(chs.begin(), chs.begin()+k)){
            max_c = max(max_c, el.c);
            sum_h += el.h;
        }
        cout << max_c << ' ' << sum_h;
    }
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

 

→ 1번 실수가 고스란히 담긴 코드

---

실수 2번 출력, 여러 개의 test case가 존재하므로 개행문자 필요 ('\n' 추가)

cout << tv << ' ' << sum_h << '\n';

---

최종 솔루션 1 (priority_queue 활용)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct ch {
    ll c;
    ll h;
};

bool cmp1(ch a, ch b){
    return a.c < b.c;
}

void solve(){
    int tc; cin >> tc;
    while(tc--){
        int n, k; cin >> n >> k;

        vector<ll> cs(n); for(auto &c:cs) cin >> c;
        vector<ll> hs(n); for(auto &h:hs) cin >> h;
        vector<ch> chs(n);
        for(int i=0; i<n; i++) chs[i] = {cs[i], hs[i]};
        stable_sort(chs.begin(), chs.end(), cmp1);

        ll tv = chs[k-1].c;    // target_value
        int ti;                 // target_idx
        for(ti = n-1; ti >= 0; --ti){
            if(chs[ti].c == tv) break; 
        }

        ll sum_h = 0LL;
        priority_queue<ll> pq;
        for(int i=0; i<=ti; ++i) pq.push(chs[i].h);
        while(k--){
            sum_h += pq.top(); pq.pop();
        }

        cout << tv << ' ' << sum_h << '\n';
    }
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

 

최종 솔루션 2 (sort만 활용)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct ch {
    ll c;
    ll h;
};

bool cmp1(ch a, ch b){
    return a.c < b.c;
}

bool cmp2(ch a, ch b){
    return a.h > b.h;
}

void solve(){
    int tc; cin >> tc;
    while(tc--){
        int n, k; cin >> n >> k;

        vector<ll> cs(n); for(auto &c:cs) cin >> c;
        vector<ll> hs(n); for(auto &h:hs) cin >> h;
        vector<ch> chs(n);
        for(int i=0; i<n; i++) chs[i] = {cs[i], hs[i]};
        sort(chs.begin(), chs.end(), cmp1);

        int tv = chs[k-1].c;    // target_value
        int ti;                 // target_idx
        for(ti = n-1; ti >= 0; --ti){
            if(chs[ti].c == tv) break; 
        }

        ll sum_h = 0;
        sort(chs.begin(), chs.begin()+ti+1, cmp2);
        for(auto el:vector<ch>(chs.begin(), chs.begin()+k)){
            sum_h += el.h;
        }

        cout << tv << ' ' << sum_h << '\n';
    }
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

---

 

참고

https://codeforces.com/problemset/gymProblem/101991/I

https://drive.google.com/file/d/1AUiHZ9hsFb2AOdmtu53SdtOs_4GnsnSU/view

acpc2018_editorial.pdf