문제 개요
같은 길이를 가진 두 개의 숫자 리스트 performance와 costs, 그리고 하나의 숫자 k가 주어집니다. 각 직원 i는 performance[i] 수준으로 업무를 수행하며, 최소한 costs[i]만큼의 보수를 받아야 합니다. 이때 k명의 직원을 고용하면서, 그룹 내 다른 직원들과 비교하여 각자의 성과에 비례해 급여를 지급한다는 조건을 만족하는 최소 비용을 구해야 합니다.
입력 예시
예를 들어 performance = [5, 3, 2], costs = [100, 5, 4], k = 2라고 가정해 봅시다. 이 경우 출력은 10이 됩니다.
직원 1과 직원 2를 선택하면 두 사람은 최소 5 + 4 = 9만큼 받아야 합니다. 하지만 직원 1의 성과가 직원 2보다 1.5배 높으므로, 직원 1은 최소 1.5 × 4 = 6을 받아야 합니다. 따라서 총 지급액은 6 + 4 = 10이 됩니다.
풀이 접근 방법
이 문제는 다음 단계에 따라 해결할 수 있습니다.
- n := c의 크기로 설정합니다.
- 크기가 n인 배열 seq를 정의하고, 0부터 n−1까지의 값으로 채웁니다.
- c[i] * p[j] < c[j] * p[i] 조건, 즉 '비용 대비 성과 비율'을 기준으로 seq 배열을 오름차순 정렬합니다.
- ans := 무한대(inf), psum := 0으로 초기화합니다.
- 우선순위 큐 pq를 정의합니다.
- i := 0부터 i < n까지 반복하면서 다음을 수행합니다.
- idx := seq[i]
- p[idx]를 pq에 삽입하고, psum에 p[idx]를 더합니다.
- pq의 크기가 k보다 커지면, psum에서 pq의 최상단(top) 값을 빼고 해당 요소를 제거합니다.
- i ≥ k − 1일 때, ans := min(ans, c[idx] / p[idx] * psum)으로 갱신합니다.
- 최종적으로 ans를 반환합니다.
핵심 아이디어는 다음과 같습니다. 직원들을 '임금/성과' 비율 순으로 정렬한 뒤, 현재 탐색 중인 직원을 그룹 내 비율이 가장 높은 사람으로 간주합니다. 앞서 살펴본 직원들은 모두 현재 직원보다 비율이 낮거나 같으므로, 현재 직원의 비율로 급여를 계산해도 최저 임금 조건을 만족합니다. 여기에 최대 힙을 활용해 성과 값이 가장 큰 직원을 제거함으로써, 항상 k명 중 성과 합이 가장 작은 조합을 유지하면 최적의 답을 얻을 수 있습니다.
C++ 구현 예시
#include <bits/stdc++.h>
using namespace std;
double solve(vector<int>& p, vector<int>& c, int k) {
int n = c.size();
vector<int> seq(n);
for (int i = 0; i < n; ++i)
seq[i] = i;
sort(seq.begin(), seq.end(), [&](int i, int j) {
return c[i] * p[j] < c[j] * p[i];
});
double ans = INT_MAX, psum = 0;
priority_queue<int> pq;
for (int i = 0; i < n; ++i) {
int idx = seq[i];
pq.emplace(p[idx]);
psum += p[idx];
if (pq.size() > k) {
psum -= pq.top();
pq.pop();
}
if (i >= k - 1)
ans = min(ans, (double)c[idx] / p[idx] * psum);
}
return ans;
}
int main(){
vector<int> performance = {5, 3, 2};
vector<int> costs = {100, 5, 4};
int k = 2;
cout << solve(performance, costs, k);
}
실행 결과
입력:
{5, 3, 2}, {100, 5, 4}, 2
출력:
10
복잡도 및 마무리
이 알고리즘은 정렬에 O(n log n), 힙 연산에 O(n log k)의 시간이 소요되므로 전체적으로 O(n log n) 안에서 문제를 해결할 수 있습니다. '비율 기준 정렬 + 힙으로 최적 조합 유지' 패턴은 최저 임금 조건이 있는 고용 문제처럼 비율과 누적합이 결합된 최적화 문제에서 자주 등장하므로, 응용 가능성이 높은 기법이니 잘 기억해 두면 좋습니다.