BOJ 29202 - 책가방 (D5)

2023 KSA Automata G번이다. 아레나 당시에 27점까지 긁었는데, 27점 풀이로 44점까지 긁을 수 있었다는 걸 대회 때 알았으면 더 좋았을 것 같다.

 

사용 알고리즘

Segment Tree + 좌표 압축 && 그리디 (우선순위 큐)

 

풀이

일단 섭태3을 풀어보자. 부피의 최댓값만 고려하면 되므로 부피 기준으로 오름차순으로 정렬하고 정렬된 배열에서 x번 책을 고르면, 1~x-1 사이 책은 모두 부피가 \( V_{x} \) 이하이다. 따라서 이 중에서 무게가 작은 k-1개를 골라주는게 이득이다. 이는 우선순위 큐(max heap)의 크기를 k-1으로 유지하고, 하나의 변수를 관리하는 것으로 해결할 수 있다.

    for(int i = 0 ; i < n ; i++)v[i].i=i+1;
    sort(all(v), cmp);
    priority_queue<ll> pq;
    ll sum = 0;
    for(int i = 0 ; i < k-1 ; i++){
        pq.push(v[i].w);
        sum += v[i].w;
    }
    ll ans = 1e18;
    for(int i = k-1 ; i < n ; i++){
        ans = min(ans, sum+v[i].w+v[i].v);
        pq.push(v[i].w);
        sum += v[i].w-pq.top();
        pq.pop();
    }
    cout<<ans<<endl;
    priority_queue<pair<ll,ll>> Pq;
    sum=0;
    for(int i = 0 ; i < k-1 ; i++){
        Pq.push({v[i].w,v[i].i});
        sum += v[i].w;
    }
    for(int i = k-1 ; i < n ; i++){
        if(ans==sum+v[i].w+v[i].v){
            while(Pq.size())cout<<Pq.top().second<<" ", Pq.pop();
            cout<<v[i].i;
            exit(0);
        }
        Pq.push({v[i].w,v[i].i});
        sum += v[i].w-Pq.top().first;
        Pq.pop();
    }

여기서 T까지 하나 고정하고 저 함수를 쓰면 섭태4까지 풀 수 있다.

이제 만점 풀이를 보자. 마찬가지로 V 기준으로 오름차순으로 정렬한 후, i번을 보고 있다고 하자. 일단 i번을 고른다. 그리고 이번에는 k-1개가 아닌, k-2개만 무게가 가장 작은 책을 골라준다.

그리고 나머지 1개의 책은 T를 결정해줄 건데, 여기서 고르지 않은 가장 작은 T가 이미 골라진 책들 중에 가장 작은 T 이상일 수 있다. 즉 T가 갱신되지 않을 수 있다. 따라서 이 경우에 대해 케이스를 나눠줄 것이다. 

\( t \) 를 지금까지 고른 k-1개의 책 중 가장 작은 T 값이라 하자. 그리고 j번 책을 추가한다고 하자.

 

(i) \( T_{j} \) 가 \( t \) 이상인 책을 고를 때

T는 갱신되지 않고, V도 당연히 갱신되지 않는다. (1~i-1에서 고를 것이고, 오름차순이므로)

따라서 \( W_{j} \) 만큼 갱신된다

 

(ii)  \( T_{j} \) 가 \( t \) 미만인 책을 고를 때

V는 (i)처럼 갱신되지 않지만, T는 갱신된다.

T가 \( T_{j} \)로 대체되므로, \( W_{j} + T_{j} - t \) 라고 할 수 있다.

 

위 두가지 경우를 모두 고려해주면 된다. 위 값을 빠르게 구하려면, 지금까지 지났던 i 중 \( W_{i} \) 의 최솟값과 \( W_{i} + T_{i} \) 의 최솟값을 빠르게 구해야 하고 이는 세그먼트 트리로 해결할 수 있다. 세그먼트 트리는 3개를 이용한다.

1. \( t \)를 구하는 세그

2. \( W_{i} \) 의 최솟값을 구하는 세그

3. \( W_{i} + T_{i} \) 의 최솟값을 구하는 세그

2,3번 세그먼트 트리를 쓸 때 \( t \)에 따라 범위를 설정해야 하므로 좌표압축이 필요하다. 좌표압축할 때 T값이 같은 원소가 있으면 세그먼트 트리가 꼬이므로 좌표압축을 {값, 인덱스}까지 저장한 후 수행해야 한다.

 

이렇게 하면 답을 구할 수 있고, 세그먼트 트리에 인덱스까지 pair로 관리하면 역추적까지 할 수 있다.

아래 정답 코드는 디버깅의 흔적과 노가다 때문에 더러울 수 있다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef long long ll;
ll n, k;
struct asdf{
    ll w,v,t,i;
};
bool cmp(asdf a, asdf b){return a.v<b.v; }
bool cmp2(asdf a, asdf b){ return a.t<b.t; }
struct segtree{
    vector<ll> tree;
    segtree(): tree(808080,1e18) {}
    void upd(ll node, ll s, ll e, ll idx, ll diff){
        if(idx<s or e<idx)return;
        if(s==e)tree[node]=diff;
        else{
            ll mid = s+e>>1;
            upd(node*2,s,mid,idx,diff);
            upd(node*2+1,mid+1,e,idx,diff);
            tree[node] = min(tree[node*2],tree[node*2+1]);
        }
    }
    ll query(ll node, ll s, ll e, ll l, ll r){
        if(l>r)return 1e18;
        if(e<l or r<s)return 1e18;
        if(l<=s and e<=r)return tree[node];
        ll mid = s+e>>1;
        return min(query(node*2,s,mid,l,r),query(node*2+1,mid+1,e,l,r));
    }
} seg;
struct segtree2{
    vector<pair<ll,ll>> tree;
    segtree2(): tree(808080,{1e18,1e18}) {}
    void upd(ll node, ll s, ll e, ll idx, pair<ll,ll> diff){
        if(idx<s or e<idx)return;
        if(s==e)tree[node]=diff;
        else{
            ll mid = s+e>>1;
            upd(node*2,s,mid,idx,diff);
            upd(node*2+1,mid+1,e,idx,diff);
            tree[node] = min(tree[node*2],tree[node*2+1]);
        }
    }
    pair<ll,ll> query(ll node, ll s, ll e, ll l, ll r){
        if(l>r)return {1e18,1e18};
        if(e<l or r<s)return {1e18,1e18};
        if(l<=s and e<=r)return tree[node];
        ll mid = s+e>>1;
        return min(query(node*2,s,mid,l,r),query(node*2+1,mid+1,e,l,r));
    }
} wseg, wtseg;
vector<pair<ll,ll>> c;
ll cp(pair<ll,ll> x){
    return lower_bound(all(c), x)-c.begin()+1;
}
void s(vector<asdf> &v){
    for(int i = 0 ; i < n ; i++){
        v[i].i=i+1;
    }
    sort(all(v), cmp);
    priority_queue<tuple<ll,ll,ll>> pq;
    ll sum = 0;
    for(int i = 0 ; i < k-2 ; i++){
        pq.push({v[i].w,v[i].i,v[i].t});
        sum += v[i].w;
        seg.upd(1,1,n,v[i].i,v[i].t);
    }
    ll ans = 1e18;
    for(int i = k-2 ; i < n ; i++){
        seg.upd(1,1,n,v[i].i,v[i].t);
        ll t = seg.query(1,1,n,1,n);
        ll res1 = sum+v[i].w+v[i].v+t;
        ll res2 = res1;
        res1 += wseg.query(1,1,n,cp({t,1e18}),n).first;
        res2 += wtseg.query(1,1,n,1,cp({t,1e18})).first-t;
        ans = min({ans, res1, res2});
        pq.push({v[i].w,v[i].i,v[i].t});
        auto [A,B,C] = pq.top();
        seg.upd(1,1,n,B,1e18);
        wseg.upd(1,1,n,cp({v[i].t,v[i].i}),{1e18,1e18});
        wtseg.upd(1,1,n,cp({v[i].t,v[i].i}), {1e18,1e18});
        wseg.upd(1,1,n,cp({C,B}),{A,B});
        wtseg.upd(1,1,n,cp({C,B}),{A+C,B});
        sum += v[i].w-A;
        pq.pop();
    }
    cout<<ans<<endl;
    while(pq.size())pq.pop();
    sum = 0;
    for(int i = 1 ; i <= n ; i++)wseg.upd(1,1,n,i,{1e18,1e18}), wtseg.upd(1,1,n,i,{1e18,1e18}), seg.upd(1,1,n,i,1e18);
    for(int i = 0 ; i < k-2 ; i++){
        pq.push({v[i].w,v[i].i,v[i].t});
        sum += v[i].w;
        seg.upd(1,1,n,v[i].i,v[i].t);
    }
    for(int i = k-2 ; i < n ; i++){
        seg.upd(1,1,n,v[i].i,v[i].t);
        ll t = seg.query(1,1,n,1,n);
        ll res1 = sum+v[i].w+v[i].v+t;
        ll res2 = res1;
        res1 += wseg.query(1,1,n,cp({t,1e18}),n).first;
        res2 += wtseg.query(1,1,n,1,cp({t,1e18})).first-t;
        if(min(res1,res2)==ans){
            cout<<v[i].i<<" ";
            while(pq.size()){
                auto [A,B,C] = pq.top();
                cout<<B<<" ";
                pq.pop();
            }
            if(res1<=res2)cout<<wseg.query(1,1,n,cp({t,1e18}),n).second;
            else cout<<wtseg.query(1,1,n,1,cp({t,1e18})-1).second;
            exit(0);
        }
        ans = min({ans, res1, res2});
        pq.push({v[i].w,v[i].i,v[i].t});
        auto [A,B,C] = pq.top();
        seg.upd(1,1,n,B,1e18);
        wseg.upd(1,1,n,cp({v[i].t,v[i].i}),{1e18,1e18});
        wtseg.upd(1,1,n,cp({v[i].t,v[i].i}), {1e18,1e18});
        wseg.upd(1,1,n,cp({C,B}),{A,B});
        wtseg.upd(1,1,n,cp({C,B}),{A+C,B});
        sum += v[i].w-A;
        pq.pop();
    }
}
int main(){
    fast;
    cin>>n>>k;
    vector<asdf> v(n);
    if(k==1){
        ll ans=1e18;
        ll res=0;
        for(int i = 1 ; i <= n ; i++){
            ll a,b,c; cin>>a>>b>>c;
            if(ans>a+b+c){
                ans=a+b+c;
                res=i;
            }
        }
        cout<<ans<<endl<<res;
        return 0;
    }
    for(int i = 0 ; i < n ; i++)cin>>v[i].w>>v[i].v>>v[i].t, v[i].i=i+1, c.push_back({v[i].t,i+1});
    sort(all(c)); comp(c);
    s(v);
}

풀이는 재밌는데 구현 때문에...

아마 set이나 map을 쓰면 더 간단하게 될 것 같아서 다음에 도전해 보겠다.