[C++] 백준 23843번: 콘센트

문제 링크

23843번: 콘센트

문제 요약

전자기기들을 충전하는데 걸리는 시간과 콘센트의 수가 주어진다. 전자기기의 충전 시간은 2의 거듭제곱꼴이다. 전자기기들을 모두 충전하는데 걸리는 시간의 최솟값을 구해야 한다.

접근 방법

직감에 의거해 그리디 알고리즘으로 풀었지만 증명은 따로 하지 않았습니다.

1. 입력을 내림차순으로 정렬해 M개만 오름차순의 우선순위 큐에 넣는다.
2. 나머지 N - M개에 대해 우선순위 큐의 top에 현재 원소를 더해준다.
3. 우선순위 큐에서 원소를 하나 빼고 모두 제거한다.
4. 하나 남은 원소를 출력한다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	cin >> n >> m;

	priority_queue<int, vector<int>, greater<int>> pq;
	vector<int> v(n);

	for (int i = 0; i < n; i++)
		cin >> v[i];

	sort(v.begin(), v.end(), greater<>());
	for (int i = 0; i < min(m, n); i++)
		pq.push(v[i]);

	for (int i = m; i < n; i++)
	{
		int top = pq.top();
		pq.pop();
		pq.push(v[i] + top);
	}

	while (pq.size() != 1)
		pq.pop();

	cout << pq.top() << '\n';
	return 0;
}