BOJ 17612 - 쇼핑몰

체감으로는 골드 4?정도로 느껴지는 우선순위큐를 잘 활용하는 법을 안다면 쉽게 구현할 수 있는 문제라고 생각한다.

문제를 꼼꼼히 읽으면 쉽게 접근법을 찾아낼 수 있다. 우선 요구사항을 정리하면 다음과 같다.

 

1. 계산대에 줄을 선 순서대로 고객이 들어온다.

 

2. 빨리 계산이 끝나는 계산대에 고객을 안내하고, 기다려야 하는 시간이 같다면 계산대 번호가 작은 순서대로 고객을 안내한다.

 

3. 계산이 끝나는 대로 고객이 나간다. 계산을 마친 고객이 여러 명이라면 계산대 번호가 큰 순서대로 나간다.

 

기본적으로 계산대에 사람이 있어야 하므로 처음 $min(k, n)$명에게 순서대로 계산대에 배정한다.

이제 계산이 가장 빨리 끝나는 계산대의 시간을 $t$라고 해보자, 다음 손님이 왔을 때 그 계산대에서 계산을 끝마치는 시간은 $t$+$w_i$라고 볼 수 있다. 만약 빨리 끝나는 계산대가 여러 개라면 2번 조건에 맞게 배정한다. 답을 구하기 위해선 나가는 손님들의 순서가 중요하다. 나가는 손님들의 시간을 전부 관리하면서 3번 조건에 따라 답을 구할 수 있다.

 

#define _CRT_SECURE_NO_WARNING
#include <bits/stdc++.h>
#include <ext/rope>
#include <cassert>
#include <x86intrin.h>
using namespace std;
using namespace __gnu_cxx;

// utils
#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())
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

// gcd, lcm, egcd funcs
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);}
// builtin funcs
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);}
// debuging funcs
#define deb(x) cout<<#x<<": "<<(x)<<endl

//search for array
int dx[]={1,-1,0,0,0,0};
int dy[]={0,0,1,-1,0,0};
int dz[]={0,0,0,0,1,-1};
//////////////////////////////////////////
struct shopping{
	ll id,w,num;
	bool operator<(const shopping&d) const{
		if(w==d.w)return num>d.num;//시간 같다면 가장 작은 번호로
		return w>d.w;
	}
};
struct outshop{
	ll id,w,num;
	bool operator<(const outshop&d) const{
		if(w==d.w)return num<d.num;//시간 같다면 가장 높은 번호로
		return w>d.w;
	}
};
int main(){
	fastio;
	int n,k;
	cin>>n>>k;
	vector<pair<ll,ll>>arr(n);
	for(auto&[a,b]:arr)cin>>a>>b;//id, w

	priority_queue<shopping>pq;
	for(int i=0; i<min(k,n); i++)pq.push({arr[i].first,arr[i].second,i+1});
	
	priority_queue<outshop>oq;
	for(int i=k; i<n; i++){
		shopping save=pq.top();
		pq.pop();
		oq.push({save.id,save.w,save.num});
		pq.push({arr[i].first,save.w+arr[i].second,save.num});
	}
	while(!pq.empty()){
		shopping save=pq.top();
		pq.pop();
		oq.push({save.id,save.w,save.num});
	}
	ll now=1,ans=0;
	while(!oq.empty()){
		ans+=oq.top().id*now;
		oq.pop();
		now++;
	}
	cout<<ans;
	return 0;
}