[G5] 백준 13164번 행복 유치원 C++ 그리디 알고리즘, 우선순위 큐

리뷰

 

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

N명의 인원을 K개의 그룹으로 나누고, 각 그룹에서 키가 가장 큰 학생과 작은 학생의 차이의 합의 최소값을 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 학생의 수를 저장할 변수
• k : 그룹의 수를 저장할 변수
• h : 학생의 키를 저장할 변수

 

함수

없음

 

 

문제풀이

1. n, k, h값을 입력 받고, 변수 prev를 h로 초기화한다.
2. 정수형 내림차순으로 정렬하는 우선순위 큐 pq를 초기화한다.
3. n-1명의 키 정보를 변수 h에 입력받는다.
4. pq에 h-prev값을 추가하고, prev를 h로 갱신한다.
5. pq에서 k-1개의 요소를 pop()처리한다.
6. long long타입 변수 ans를 0으로 초기화한다.
7. pq가 빌때까지 ans에 pq의 top()요소의 값을 더해주고, pop()처리한다.
8. ans에 저장된 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. N(1 ≤ N ≤ 300,000) ,K(1 ≤ K ≤ N), 원생의 키는 10^9를 넘지 않는 자연수이다.
2. 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다.
3. 원생의 키 차이를 pq에 삽입하고, k개의 조를 짤 수 있으므로 k-1개의 조만큼의 키 차이를 제거해주었다.
4. 나머지 조의 키 차이는 필연적이기 때문에 ans에 더해주되, int범위를 넘어설 수 있으므로 long long타입으로 정했다.

 

정답 코드

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

const int N = 3e5;
int n, k, h;

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

	cin >> n >> k >> h;
	int prev = h;
	priority_queue<int> pq;
	for (int i = 1; i < n; ++i) {
		cin >> h;
		pq.push(h - prev);
		prev = h;
	}

	while (--k) pq.pop();
	long long ans = 0;
	while (!pq.empty()) {
		ans += pq.top(); pq.pop();
	}

	cout << ans;
}