BOJ 15590 Rental Service

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

15590번: Rental Service

 

우유를 많이 생산사는 소 들은 젖을 짜서 팔고, 덜 생산하는 소들은 빌려주는 것이 이득이다. 그 경계를 어떻게 설정해야하는지 생각해야하는 것이 문제이다.

나는 소 우유 생산량으로 오름차순 정렬을 하고, 0~i 의 소들은 빌려주고,  i~ n-1 소들은 젖을 짰을 때 벌 수 있는 돈을 모든 i (0 ~ n-1)에 대해 해 보았다.

이때, 소들을 빌릴 때 얻을 수 있는 비용을 내림차순 정렬 후 누적합을 사용하여 k 마리의 소를 빌려주었을 때 얻을 수 있는 돈을 O(1) 에 구하게 만들었다.

문제는, 생산 우유량인데, 위의 아이디어에서 착안하여 우유 가격이 낮은 순으로 정렬한 뒤, k ~ m-1 의 상점에 우유를 팔았을 때 벌 수 있는 돈과 우유량을 누적합을 저장했고, l 만큼 우유를 팔았을 때 벌 수 있는 돈은 lower_bound (기준 :  우유 량)를 적용하여 O (log n)에 구하게 만들었다.

lower bound 를 통해 얻은 인덱스를 i라 했을 때,

#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ull;
ull n,m,r, a,b , answer;
vector<pair<ull, ull>> store;
vector<pair<ull, ull>> store_psum;
vector<ull> neighbor;
vector<ull> neighbor_psum;
vector<ull> cow;
vector<ull> cow_psum;



//reverse upper bound
ull get_milk_cost(ull target){

    

    auto it = lower_bound(store_psum.rbegin(), store_psum.rend(), pair<ull, ull>(0, target), 
                [](pair<ull, ull> lhs, pair<ull, ull> rhs ) {return lhs.second > rhs.second;}) ;
                 

    //printf("%d %d %d\n", idx - store_psum.rbegin(), idx->first, idx->second );
    ull earn = 0;
    ull idx = m - 1 - (it - store_psum.rbegin()) ;
    
    if(idx == m-1){
        earn = store[idx].first * min(target, store[idx].second);
    }
    else {
        earn = store_psum[idx+1].first + \
                store[idx].first * (
                    min(target - store_psum[idx+1].second, store[idx].second));
    }
    return earn;
    
}

int main(){

    scanf("%llu%llu%llu",&n,&m,&r);
    neighbor_psum.resize(r);
    store_psum.resize(m);
    cow_psum.resize(n);
    
    for(ull i=0;i<n;i++){
        scanf("%lld",&a); 
        cow.push_back(a);
    }

    for(ull i=0;i<m;i++){
        scanf("%lld%lld",&a,&b);
        store.push_back({b,a}); //to sort
    }
    for(ull i=0;i<r;i++){
        scanf("%lld",&a);
        neighbor.push_back(a);
    }
    sort(cow.begin(), cow.end());
    sort(store.begin(), store.end());
    sort(neighbor.begin(), neighbor.end(), greater<>());
    
    

    neighbor_psum[0]=neighbor[0];
    for(ull i=1;i<r;i++) neighbor_psum[i] = neighbor_psum[i-1] + neighbor[i];
    store_psum[m-1].second = store[m-1].second;
    store_psum[m-1].first  = store[m-1].second * store[m-1].first;
    
    //return 0;
    for(ull i=m-2;i>=0;i--){
        store_psum[i].second = store_psum[i+1].second + store[i].second;
        store_psum[i].first  = store_psum[i+1].first + store[i].first*store[i].second;
    }
    //return 0;
    cow_psum[n-1] = cow[n-1];
    for(ull i=n-2;i>=0;i--){ cow_psum[i] = cow_psum[i+1] + cow[i]; }

	
    //모든 소에서 생산한 것을 milk로 팔 때
    answer = get_milk_cost(cow_psum[0]);
    //return 0;
    for(ull i=0;i<n;i++){
        ull milk = 0, rent = 0;
        if(i+1 < n) milk = get_milk_cost(cow_psum[i+1]);
        if(i < r) rent = neighbor_psum[i];
        else rent = neighbor_psum[r-1];
        if(milk + rent > answer) answer = milk + rent;
        //printf("%d %d %d\n",milk, rent, answer);
    }

    printf("%lld\n",answer);

    return 0;
}

 

하지만, 위의 답은 맞지 않았다.

디버깅하기 어려워 새롭게 code 를 작성했다. 이때, 변경점은 다음과 같다.
1. cow, neighbor 는 누적합을 구할 필요가 없다. (메모리 감소)
2. store 정렬 시에 우유 값을 기준으로 정렬한다. (lower bound 사용하지 않음)
3. store_psum 대신 이 두개를 분리한 store_cost_psum, store_gallon_psum 를 사용 (디버깅 용이)
4. i 가 늘어남에 따라 팔 수 있는 우유량은 감소하므로, store의 idx (now_store)를 찾기 위해 이전 판매를 진행했던 store의 idx를 사용한다. 이후 store_gallon_psum[now_store + 1] <= milk_gallon 을 만족하는 상점이 나올 때 까지 idx를 증가시킨다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

typedef long long ll;

int n,m,r;
ll answer;

vector<ll> neighbor;
vector<ll> cow;
vector<pair<ll,ll>> store;
vector<ll> store_cost_psum, store_gallon_psum;

int now_store = 0;
ll get_milk_cost(ll milk_gallon){
    ll milk_cost = 0;
    while(true){
        if(store_gallon_psum[now_store + 1] <= milk_gallon){
            milk_cost = store_cost_psum[now_store + 1] + store[now_store].second * min(store[now_store].first, milk_gallon - store_gallon_psum[now_store + 1]);
            break;
        }
        else{
            now_store += 1;
        }
    }

    return milk_cost;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> m >> r;

    cow.resize(n);
    store.resize(m);
    store_cost_psum.resize(m);
    store_gallon_psum.resize(m);
    neighbor.resize(r);

    for(int i=0;i<n;i++) cin >> cow[i];
    for(int i=0;i<m;i++) cin >> store[i].first>> store[i].second; //gallon, cost
    for(int i=0;i<r;i++) cin >> neighbor[i];

    sort(neighbor.begin(), neighbor.end(), greater<>());
    sort(cow.begin(), cow.end());
    sort(store.begin(), store.end(), [](pair<ll, ll> lhs, pair<ll, ll> rhs){return lhs.second < rhs.second;}); //오름차순

    ll rent_cost = 0, milk_gallon = 0, milk_cost = 0;
    for(ll c : cow)  milk_gallon += c;

    /*
    store_cost_psum[i] : i ~ m-1 까지의 총 수익
    store_gallon_psum[i] : i ~ m-1 까지의 총 gallon 수
    */
    
    store_cost_psum[m-1] = store[m-1].second * store[m-1].first;
    store_gallon_psum[m-1] = store[m-1].first; 
    for(int i=m-2;i>=0;i--){
        store_cost_psum[i] = store_cost_psum[i+1] + store[i].first * store[i].second;
        store_gallon_psum[i] = store_gallon_psum[i+1] + store[i].first;
    }
    store_gallon_psum.push_back(0);
    store_cost_psum.push_back(0);


    answer = get_milk_cost(milk_gallon);
    //0~i : rent, i+1 ~ n : milk
    for(int i=0;i<n;i++){
        milk_gallon -= cow[i];
        if(i < r) rent_cost += neighbor[i];
        milk_cost = get_milk_cost(milk_gallon);
        if(rent_cost + milk_cost > answer) answer = rent_cost + milk_cost;
    }
    
    cout << answer << "\n";
    return 0;
}

 

애매하다 싶으면 코드를 다시짜는 것도 답인 것 같다. 첫번째 코드를 고쳐보겠다고 여러번 제출했는데, 좋은 시도는 아닌 것 같다.