[BOJ] 23843번 콘센트 (C++)

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

23843번: 콘센트

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> time(n);
	for(int i = 0; i < n; i++){
		cin >> time[i];
	}
	sort(time.begin(), time.end(), greater<>());
	
	if(m > n){   // 예외처리
		cout << time[0] << endl;
		return 0;
	}

	priority_queue<int, vector<int>, greater<int>> pq;
	for(int i = 0; i < m; i++){
		pq.push(time[i]);
	}
	for(int i = m; i < n; i++){
		int t = pq.top() + time[i];
		pq.pop();
		pq.push(t);
	}
	
	for(int i = 0; i < m - 1; i++) pq.pop();
	cout << pq.top() << endl;
	return 0;
}

 

1. 충전에 필요한 시간을 내림차순으로 정렬한다. (많은 시간이 걸리는 전자기기부터 충전)

2. m개의 전자기기를 충전시킨다.

3. 먼저 충전이 끝나는 콘센트(오름차순 우선순위큐)부터 다음으로 충전 시간이 긴 기기를 충전시킨다.

4. 가장 오래 충전하는 콘센트의 시간을 출력한다.

 

** m > n일 때는 예외처리: 가장 충전 시간이 긴 전자기기 값이 정답이다.