(12456) 모닝커피 (Large)

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

단계별로 풀어보기

42단계(그리디 알고리즘 2) 8번째

 

 

 

일수 K의 범위는 int 범위를 아득히 뛰어넘으므로 O(K)인 알고리즘은 절대 답이 아니다. ci나 ti도 마찬가지다.

문제와 K의 의미(날짜)의 특성을 생각해보면 log K나 √K 같은 시간복잡도를 갖기도 어렵다고 볼 수 있다.

여기서 커피의 종류 N의 범위는 100밖에 안 되므로 N을 기준으로 순회하는 어떤 알고리즘을 써야 한다고 추측할 수 있다.

 

커피를 유통기한이 긴 순서대로 정렬한 뒤, 마지막 날부터 탐색한다고 하자. 가능한 커피 중 가장 만족도가 커피를 마시는 것이 좋다. 어차피 이날 가능한 커피는 그 전에도 마실 수 있기 때문이다. 날짜가 내려오다가 다음 커피의 유통기한을 만나면 이제 그 커피도 마실 수 있는 커피 리스트에 들어간다. 가능한 커피 중 만족도가 높은 커피는 우선순위 큐로 찾으면 된다.

당연히 K를 1씩 탐색하면 시간 초과가 난다. 우선순위 큐의 원소가 갱신되는 경우는 어떤 커피의 유통기한일 때 뿐이므로 커피의 유통기한을 기준으로 구간을 나눠 구간 단위로 계산을 하면 된다.

남은 기간보다 이번 만족도를 가진 커피 수가 더 적다면 전부 마신 뒤 남은 기간에서 빼준 뒤 다음 커피를 꺼내고, 더 많다면 남은 기간 전부 이번 커피를 마시고 남은 개수만큼 다시 우선순위 큐에 집어넣는다. 이때 첫날부터 가장 유통기한 짧은 커피까지 기간을 쉽게 계산하기 위해 유통기한이 0일인 가상의 더미 데이터 커피를 추가로 넣는다.

 

 

 

#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <algorithm>
using namespace std;
typedef tuple<long,long,int> tp; // 커피개수, 유통기한, 만족도

long solve(){
  int n;
  long k;
  
  cin >> n >> k;
  
  vector<tp> v(n+1);
  
  for(int i=1;i<=n;i++){
    cin >> get<0>(v[i]) >> get<1>(v[i]) >> get<2>(v[i]);
  }
  
  sort(v.begin(), v.end(), [](tp &A, tp &B){
    return get<1>(A) > get<1>(B);
  });
  
  auto cmp= [&](tp &A, tp &B) -> bool {
    return get<2>(A) < get<2>(B);
  };
  priority_queue<tp, vector<tp>, decltype(cmp)> pq(cmp);
  
  long nowday= k, ans= 0;
  
  for(int i=0;i<=n;i++){
    long nextday= get<1>(v[i]);
    long period= nowday-nextday;
    
    while(!pq.empty() && period>0){
      tp now= pq.top();
      pq.pop();
      
      if(period>=get<0>(now)){
        ans+= get<0>(now)*get<2>(now);
        period-= get<0>(now);
      }else{
        ans+= period*get<2>(now);
        get<0>(now)-= period;
        pq.push(now);
        period= 0;
      }
    }
    
    nowday= nextday;
    pq.push(v[i]);
  }
  
  return ans;
}

int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  for(int i=1;i<=T;i++){
    cout << "Case #" << i << ": " << solve() << "\n";
  }
  
  return 0;
}

 

 

 

이건 예전에 푼 방식인데, 마지막 날부터 내려오는 것이 아닌 첫날부터 올라가는 방식으로 푸는 알고리즘이다.

커피를 유통기한이 짧은 순서대로 하나씩 탐색하며 첫날부터 유통기한까지 가능한 날(대응되는 커피가 없거나 있어도 이번 커피보다 만족도가 낮을 때)에 이번 커피를 대응시킨다. 값 갱신이 필요해서 기간을 탐색 중에 쪼개야 하는데다 매우 헷갈리기 때문에 위쪽처럼 푸는 게 훨 나아보인다.

#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <algorithm>
using namespace std;
typedef tuple<long,long,int> tp;

long solve(){
  int n;
  long k;
  
  cin >> n >> k;
  
  vector<tp> v(n); // 커피개수, 유통기한, 만족도
  
  for(int i=0;i<n;i++){
    cin >> get<0>(v[i]) >> get<1>(v[i]) >> get<2>(v[i]);
  }
  
  sort(v.begin(), v.end(), [](tp &A, tp &B){
    return get<1>(A) < get<1>(B);
  });
  
  auto cmp= [&](tp &A, tp &B) -> bool {
    if(get<2>(A) == get<2>(B))  return get<1>(A) > get<1>(B);
    return get<2>(A) > get<2>(B);
  };
  priority_queue<tp, vector<tp>, decltype(cmp)> pq(cmp); // 시작일, 끝일, 만족도
  pq.push(make_tuple(1,k,0));
  
  for(int i=0;i<n;i++){
    vector<tp> tmp;
    
    while(!pq.empty()){
      tp now= pq.top();
      
      if(get<2>(now)>=get<2>(v[i])) break; // 이제 만족도가 높은 케이스만 남으면 break
      
      pq.pop();
      
      if(get<0>(now)>get<1>(v[i])){ // 기간이 유통기한보다 뒤
        tmp.push_back(now);
      }else if(get<1>(now)<=get<1>(v[i]) && get<1>(now)-get<0>(now)+1<=get<0>(v[i])){ // 기간도 되고 개수도 됨
        tmp.push_back(make_tuple(get<0>(now),get<1>(now),get<2>(v[i])));
        get<0>(v[i])-= get<1>(now)-get<0>(now)+1;
      }else{
        long day= min(get<0>(now)+get<0>(v[i])-1,get<1>(v[i]));
        tmp.push_back(make_tuple(get<0>(now),day,get<2>(v[i])));
        tmp.push_back(make_tuple(day+1,get<1>(now),get<2>(now)));
        get<0>(v[i])-= day-get<0>(now)+1;
      }
      
      if(!get<0>(v[i])) break; // 남은 커피가 없으면 break
    }
    
    for(tp elem:tmp)  pq.push(elem);
  }
  
  long ans= 0;
  while(!pq.empty()){
    tp now= pq.top();
    pq.pop();
    
    ans+= (get<1>(now)-get<0>(now)+1)*get<2>(now);
  }
  
  return ans;
}

int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  for(int i=1;i<=T;i++){
    cout << "Case #" << i << ": " << solve() << "\n";
  }
  
  return 0;
}