[Programmers/프로그래머스][C++] 신입사원 교육 (PCCP 모의고사 2회 2번)

문제

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

프로그래머스 신입사원 교육

 

문제 내용

교육에는 신입사원 2명이 필요하다.

교육 이후에는 서로의 능력을 흡수하여, 두 신입사원의 능력치는 공부 전 두 사람의 능력치의 합이 된다.

신입사원들의 능력치와 총 교육 횟수를 입력받아, 모든 교육 이후에 능력치 합이 최소가 되도록 하고 싶다.

(한 번 교육을 받은 사원은, 다시 선발될 수 있다.)

 

문제 풀이

모든 교육 이후에 능력치의 합이 최소가 되려면, 매 교육마다 능력치가 제일 작은 2명을 골라야 한다.

이를 위해 priority_queue를 사용하여, 매번 가장 작은 능력치를 뽑으면 된다.

 

코드

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> ability, int number) {
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int i=0;i<ability.size();i++){
        pq.push(ability[i]);
    }
    
    while(number--){
        int people1=pq.top();
        pq.pop();
        int people2=pq.top();
        pq.pop();
        
        pq.push(people1+people2);
        pq.push(people1+people2);
    }

    int answer = 0;
    while(!pq.empty()){
        answer+=pq.top();
        pq.pop();
    }
    return answer;
}