백준 23843 콘센트

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

• 자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐

• 풀이

1. 먼저 충전해야할 전자기기들을 충전 시간이 긴 순으로 정렬한다.
2. priority queue 구조인 사용 가능한 콘센트에 전부 충전시킨다.
3. 먼저 끝나는 콘센트부터 다음으로 충전 시간이 긴 기기를 충전시킨다. 즉 priority queue의 top부터 갱신한다.
4. 가장 오래 충전하는 콘센트의 시간을 출력한다.

• 코드

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL)
#define ll long long

int N,M,ans=0,idx=0;
priority_queue<int,vector<int>,greater<int>> qq;

int main(void){
    fast;
    cin>>N>>M;
    vector<int> v(N);
    for(int i=0;i<N;++i) cin>>v[i];
    sort(v.begin(),v.end(), greater<int>());

    if(M==1){
        for(int i=0;i<N;++i){
            ans+=v[i];
        }
        cout<<ans; return 0;
    }
    
    if(N<M){
        int mv=0;
        for(int i=0;i<N;++i) mv=max(v[i],mv);
        cout<<mv; return 0;
    }

    for(int i=0;i<M;++i) qq.push(v[i]);
    idx+=M;

    while(idx<N){
        int ns=qq.top(); qq.pop();
        while(ns<=qq.top() and idx<N){
            ns+=v[idx]; idx++;
        }
        qq.push(ns);
    }
    for(int i=0;i<M-1;++i) qq.pop();
    cout<<qq.top();
}

• M이 1일 때와 N보다 클 때는 예외처리하였다.
  ( M==1일 시 모든 충전기기의 합, M>N일 시 가장 충전 시간이 긴 전자기기의 값이 정답이다. )