[프로그래머스] 신입사원 교육 (PCCP 모의고사 #2 2번)

https://school.programmers.co.kr/learn/courses/15009/lessons/121688

프로그래머스

프로그래머스 - 신입사원 교육 (PCCP 모의고사 #2 2번)

문제 유형 : 그리디, 우선순위 큐

문제 난이도 : Level 2(개인적인 체감. 문제 자체는 쉬우나, 우선순위 큐에 대한 사전지식 요구 자체가 레벨2급이라고 생각해서)

 

 

문제 설명

산업스파이 민수는 A회사에 위장 취업했습니다. 이를 모르는 민수의 상사는 신입사원 교육 중 일부를 민수에게 맡겼습니다. 민수가 맡은 임무는 신입사원 중 2명을 선발하고 선발된 2명이 같이 공부하게 하는 것입니다. 모든 신입사원들의 능력치는 정수로 표현되어 있는데, 2명의 신입사원이 같이 공부하면 서로의 능력을 흡수하여 두 신입사원의 능력치는 공부 전 두 사람의 능력치의 합이 됩니다. 즉, 능력치가 3과 7인 두 사원이 같이 공부하면 두 사원의 능력치가 모두 10이 됩니다. 선발한 2인의 교육이 끝나면 민수는 다시 2인을 선발하여 교육을 진행할 수도 있습니다. 이때 한번 민수에게 선발된 사원이 다시 선발될 수도 있습니다. 민수가 교육한 신입사원들을 제외한 다른 신입사원들의 능력치는 변하지 않습니다.

 

민수는 산업스파이이기 때문에 교육 후 모든 신입사원들의 능력치의 합을 최소화하고 싶습니다. 예를 들어, 신입사원들의 능력치가 순서대로 10, 3, 7, 2이며, 민수가 2번 교육을 해야 한다면, 첫 번째 교육은 두 번째 사원과 네 번째 사원을 선발하면 두 사원의 능력치가 5가 되어 신입사원들의 능력치가 10, 5, 7, 5가 됩니다. 두 번째 교육도 두 번째 사원과 네 번째 사원을 선발하면 신입사원들의 능력치는 순서대로 10, 10, 7, 10이 됩니다. 이 경우가 교육 후 모든 신입사원들의 능력치의 합이 37로 최소가 되는 경우입니다.

 

신입사원들의 능력치를 나타내는 정수 배열 ability와 민수가 교육을 진행해야 하는 횟수를 나타내는 정수 number가 주어졌을 때, 교육 후 모든 신입사원들의 능력치의 합의 최솟값을 return 하는 solution 함수를 완성하세요.

 

 

풀이

단순하게도 신입사원들 중 가장 능력치가 낮은 두 명씩 매번 뽑아서 교육시키면 된다.

우선순위 큐를 통해서 쉽게 구현할 수 있다.

 

최소 힙의 우선순위 큐를 만든다.

우선순위 큐에 모든 각 사원들의 능력치를 넣고, 

number번만큼 다음 과정을 반복한다:

  1. 우선순위 큐에서 능력치 2개를 pop한다.

  2. 그 뒤, 합을 구한다.

  3. 합을 두 번 우선순위 큐에 삽입한다.

그 뒤, 우선순위 큐의 모든 요소를 꺼내면서 누적시키면 된다.

 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int solution(vector<int> ability, int number) {
	// 최소 힙의 우선순위 큐 생성
    priority_queue<int, vector<int>, greater<int>> pq;
    
    // 다 넣기..
    for(const auto &ab : ability) {
        pq.push(ab);
    }
    
    for(int i = 0; i < number; i++) {
    	// 굳이 변수를 두 번 안만들고, 두번 합만 시켜도 된다!
        int employeeA = pq.top();
        pq.pop();
        int employeeB = pq.top();
        pq.pop();
        int hap = employeeA + employeeB;
        
        pq.push(hap);
        pq.push(hap);
    }
    
    // 다빼면서 총합 구하기..
    int answer = 0;
    while(!pq.empty()) {
        answer += pq.top();
        pq.pop();
    }
    
    return answer;
}