BOJ 21393 - Stock

우연히 본 문제가 쉽게 관찰을 얻을 수 있어서 기분 좋게 구현을 해봤다.

결과는.. 참혹했다.

역시나 한번에 되지 않는 것인지 수많은 TLE가 나를 반겨주었다..

n log n 풀이가 안되는 줄 알았는데 그럴리가 없다고 생각해서 다시 구현해보니

그냥 구현미스였던거였..(나는 아무 생각이 없다ㅏㅏㅏㅏㅏㅏㅏㅏ)

그래도 많이 봤던 유형의 그리디가 섞여있는 문제여서 좋았(?)다

---

체감티어: G2

태그 : 그리디, 우선순위 큐

 

문제에서 3가지, i일에 얻는 주식의 양, 판매시 얻는 가치, i일에 팔 수 있는 최대 주식수가 주어진다.

일단 문제를 보자마자 알 수 있는 것은 주식을 '잘' 분배하는 문제라는 것이다.

 

분배방법은 우선순위 큐를 이용해 간단하게 판별할 수 있었다.

우선 i일에 얻는 주식의 양은 Xi, 주식의 가격은 Pi, 최대 판매 주식 수는 Mi로 기존에 가지고 있는 주식은 now로 말하겠다.

우선순위 큐에 Pi, Mi를 담는다.

이때 Mi는 min(Mi,Xi+now)이다.

우선순위를 Pi가 작은 순으로 지정해주면 준비가 끝난다.

 

내가 얻은 관찰은 다음과 같다.

 

1. now + Xi >= pq.top().M

이 경우에 다른 경우를 고려할 필요가 없다. 

따라서 현재 가지고 있는 주식을 팔수 있는 만큼 판다.

이 정보는 pq에 바로 저장한다.

 

2. now + Xi < pq.top().M

now+XI가 판매 최대치보다 적기 때문에 Pi>pq.top().P인 경우들에서 주식을 최대로 채운다.

이전에 파는 것보다 현재에 팔아서 얻는 가격이 크다면 이전에 팔았던거 회수해서 현재에 파는 것을 반복한다.

 

따라서 위 작업을 n개의 날에 적용해주면 O(n log n)에 해결할 수 있다.

개인적으로 이 문제는 boj 13873 + boj 5896인 것 같다.

 

소스코드

#define _CRT_SECURE_NO_WARNING
#include <bits/stdc++.h>
#include <cassert>
#include <x86intrin.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl "\n"
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define repair(x) x.erase(unique(all(x)),x.end())
using namespace std;
typedef long long ll; //long long. or use int64_t
typedef long double ld; //long double
const int iinf = 1e9; //integer maximum
const long long linf = 1e18; //long long maximum
const int mod = 1e9 + 9; //prime number
template<class T>T gcd(T x, T y){if (!y)return x;return gcd(y,x%y);}
template<class T>T lcm(T x, T y){return (x*y)/gcd(x,y);}
template<class T>T bitcnt(T x){return __builtin_popcount(x);}
template<class T>T bitpar(T x){return __builtin_parity(x);}
template<class T>T bitclz(T x){return __builtin_clz(x);}
template<class T>T bitctz(T x){return __builtin_ctz(x);}
struct receives{
    int get,price,max_sell;
    
};
struct cmp{
    bool operator()(const receives&a, const receives&b){
        return a.price>b.price;
    }
};
int main(){
    fastio;
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<receives>arr(n);
        for(auto&v:arr)cin>>v.get>>v.price>>v.max_sell;
        priority_queue<receives,vector<receives>,cmp>pq;
        int ans=0, stock=0;
        for(int i=0; i<n; i++){
            if(pq.empty()){
                int used=min(arr[i].max_sell,arr[i].get+stock);
                ans+=arr[i].price*used;
                pq.push({arr[i].get,arr[i].price,used});
                stock=stock+arr[i].get-used;
            }
            else if(stock+arr[i].get<arr[i].max_sell){
                int used=0;
                stock+=arr[i].get;
                used+=stock;
                ans+=stock*arr[i].price;
                arr[i].max_sell-=stock;
                stock=0;
                while(!pq.empty()){
                    if(pq.top().price>=arr[i].price or arr[i].max_sell<=0)break;
                    receives save=pq.top();
                    pq.pop();
                    int usin=min(save.max_sell,arr[i].max_sell);
                    ans-=save.price*usin;
                    ans+=arr[i].price*usin;
                    used+=usin;
                    arr[i].max_sell-=usin;
                    if(save.max_sell-usin>0)pq.push({save.get,save.price,save.max_sell-usin});
                }
                pq.push({arr[i].get,arr[i].price,used});
            }
            else{
                int used=min(arr[i].max_sell,arr[i].get+stock);
                ans+=arr[i].price*used;
                pq.push({arr[i].get,arr[i].price,used});
                stock=stock+arr[i].get-used;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}