프로그래머스 - PCCP 모의고사 2회 - 신입사원 교육

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

프로그래머스

---

문제 설명

신입사원의 능력치가 들어있는 ability라는 데이터가 있습니다.
신입사원 2명을 짝지어 교육시키면 두 신입사원 모두 능력치가 둘의 합이 됩니다.
즉, 능력치가 3과 7인 신입사원을 같이 교육시키면 두 사원의 능력치가 모두 10이 됩니다.
한번 교육된 사람도 다시 교육 시킬 수 있습니다.
신입사원의 능력치 총합을 최소화 시키도록 교육하면, 능력치의 총합이 몇인지 구하세요.

---

아이디어

가장 능력치가 낮은 2명을 계속 더하면 최소 값이 됩니다. 

---

코드

#include <bits/stdc++.h>

using namespace std;

int solution(vector<int> ability, int number) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
    for(const auto& a : ability)
    {
        pq.push(a);
    }
    for(int i = 0; i < number; ++i)
    {
        int first = pq.top(); pq.pop();
        int second = pq.top(); pq.pop();
        int teach = first+second;
        pq.push(teach); pq.push(teach);
    }
    while(!pq.empty())
    {
        answer += pq.top();
        pq.pop();
    }
    return answer;
}