Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 푸는 직원 이동 배분 문제: 최대 편차를 최소화하는 인원 배치 알고리즘

문제 설명

한 회사에 총 n명의 직원이 있다고 가정해 보겠습니다. 모든 직원은 실력에 따라 등급을 부여받으며, 등급은 1부터 k까지의 번호로 매겨집니다. 등급 i를 가진 직원의 수는 배열 skill에 저장되며, skill[i]는 등급 i를 가진 직원 수를 나타냅니다.

이제 회사에 새로운 지점이 개설되어, 실력이 서로 다른 직원들을 해당 지점으로 전출해야 하는 상황입니다. 새 지점에 보내야 할 직원 수는 m명입니다. 다양한 실력을 가진 m명의 직원을 새 지점에 배치하려면, 다음 공식을 최소화하는 지점의 직원 등급 배분표 branch를 구해야 합니다.

최소화할 공식: max(branch[i]/m − skill[i]/n)

단, branch[i] 값들의 합은 반드시 m이 되어야 하며, 우리가 구해야 할 것은 branch[i]의 각 원소입니다.

예를 들어 입력이 k = 5, n = 10, m = 25, skill = {5, 3, 2, 7, 4}라면, 출력은 12 7 5 17 10이 됩니다.

풀이 단계

이 문제는 비례 배분(largest remainder method) 기법으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  1. 각 등급의 이상적인 배정 인원을 skill[i] × m / n으로 계산합니다.
  2. 계산값의 정수 부분을 우선 배정하고, 그 합을 sum에 누적합니다.
  3. m − sum만큼의 인원이 남으면, 소수 부분이 큰 순서대로 해당 등급에 1명씩 추가 배정합니다.

이를 의사 코드로 표현하면 다음과 같습니다.

sum := 0
for initialize i := 0, when i < k, update (increase i by 1), do:
   skill[i] := skill[i] * m / n
정수 쌍(pair)을 담는 배열 a 정의
for initialize i := 0, when i < k, update (increase i by 1), do:
   c := skill[i]
   sum := sum + c
   a[i]의 첫 번째 값 := skill[i] - c
   a[i]의 두 번째 값 := i
배열 a를 정렬
배열 a를 뒤집기(내림차순)
for initialize i := 0, when i < m - sum, update (increase i by 1), do:
   skill[a[i]의 두 번째 값] := skill[a[i]의 두 번째 값] + 1
for initialize i := 0, when i < k, update (increase i by 1), do:
   skill[i] 출력

C++ 구현 예제

더 나은 이해를 돕기 위해 위 알고리즘을 C++로 구현한 코드를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

void solve(int k, int n, int m, vector<double> skill){
    int sum = 0;
    for (int i = 0; i < k; i++)
        skill[i] = skill[i] * m / n;
    vector<pair<double, int>> a(k);
    for (int i = 0; i < k; i++) {
        int c = skill[i];
        sum += c;
        a[i].first = skill[i] - c;
        a[i].second = i;
    }
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    for (int i = 0; i < m - sum; i++) {
        skill[a[i].second] += 1;
    }
    for (int i = 0; i < k; i++) {
        if (i != k - 1)
            cout << int(skill[i]) << " ";
        else
            cout << int(skill[i]) << endl;
    }
}
int main() {
    int k = 5, n = 10, m = 25;
    vector<double> skill = {5, 3, 2, 7, 4};
    solve(k, n, m, skill);
    return 0;
}

입력

5, 10, 25, {5, 3, 2, 7, 4}

출력

12 7 5 17 10

코드 동작 원리

위 코드의 동작 과정을 단계별로 살펴보면 다음과 같습니다.

  • 비례 계산: skill[i] × m / n을 통해 각 등급이 이론적으로 담당해야 할 인원을 구합니다. 예제에서는 배율이 25/10 = 2.5배이므로 {12.5, 7.5, 5.0, 17.5, 10.0}이 계산됩니다.
  • 정수 부분 배정: 각 값의 정수 부분인 {12, 7, 5, 17, 10}을 우선 배정하고, 그 합을 sum에 저장합니다.
  • 잔여 인원 처리: m에서 sum을 뺀 만큼의 인원이 남으면, pair 배열에 저장해 둔 소수 부분(first)이 큰 순서대로 해당 등급(second, 원래 인덱스)에 1명씩 추가 배정합니다. 이렇게 하면 전체 배분이 목표 인원 m과 정확히 일치하게 됩니다.

이 방식은 각 등급 간 비율의 균형을 유지하면서도 전체 오차를 최소화할 수 있어, 제한된 인원을 여러 그룹에 공평하게 나누는 다양한 상황에 응용할 수 있습니다.