[G5] 백준 23843번 콘센트 C++ 정렬, 우선순위 큐, 그리디 알고리즘

리뷰

 

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

충전에 필요한 시간을 내림차순으로 정렬하고, m개의 0을 가진 pq를 오름차순으로 정렬하여 가장 큰 수를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 전자기기의 개수를 저장할 변수
• m : 콘센트의 개수를 저장할 변수
• arr : 전자기기의 충전 시간을 저장할 1차원 정수 배열

 

함수

없음

 

 

문제풀이

1. n, m값을 입력 받고, n개의 전자제품의 충전에 필요한 시간을 입력 받아 arr배열을 초기화한다.
2. sort함수를 통해 arr배열을 내림차순으로 정렬한다.
3. 최소힙의 성질을 가진 정수형 우선순위 큐 pq를 초기화하고, pq에 m개의 0을 push해준다.
4. 배열 arr을 순회하며 변수 d에 현재 전자기기의 충전 시간을 저장한다.
5. 변수 c에 pq의 top요소의 값을 저장하고, pq를 pop처리 후 pq에 c+d를 push한다.
6. 무한 루프를 수행하고, 변수 c에 pq의 top요소의 값을 저장하고 pq를 pop처리한다.
7. pq가 비었다면 c를 출력하고 break로 무한 루프를 빠져나온다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 충전에 필요한 시간은 최대 2^15이고, N값이 최대 10000이므로 int범위 내로 통과가 가능하다.

 

정답 코드

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

const int N = 1e4;
int n, m;
int arr[N];

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

	cin >> n >> m;
	for (int i = 0; i < n; ++i) cin >> arr[i];
	sort(arr, arr + n, greater<int>());

	priority_queue<int, vector<int>, greater<int>> pq;
	while (m--) pq.push(0);

	for (int i = 0; i < n; ++i) {
		int d = arr[i];
		int c = pq.top(); pq.pop();
		pq.push(c + d);
	}

	while (1) {
		int c = pq.top();  pq.pop();
		if (pq.empty()) {
			cout << c;
			break;
		}
	}
}