C++로 구하는 m개 팀에 나뉜 n명 참가자의 최소·최대 친구 쌍 수

문제 개요

대회 참가자 N명이 각 팀에 최소 한 명 이상의 참가자가 포함되도록 M개의 팀으로 나누어졌습니다. 대회가 종료된 후에는 같은 팀에 속했던 참가자들의 모든 쌍이 서로 친구가 됩니다.

따라서 우리의 과제는 대회 종료 시점까지 형성될 수 있는 친구 쌍의 최솟값과 최댓값을 구하는 프로그램을 작성하는 것입니다.

알고리즘

최대 쌍 수 구하기

친구 쌍이 최대가 되려면 참가자들을 한 팀에 최대한 몰아 넣어야 합니다. 즉, 한 팀에 나머지 인원 전부를 배치하고 나머지 팀에는 한 명씩만 배치하면 됩니다. 이때 가장 큰 팀의 인원은 (n − m + 1)명이 되며, 이 팀에서 만들어지는 쌍의 수가 곧 전체 최댓값입니다.

maxPairs = ((n – m) * (n – m + 1)) / 2

최소 쌍 수 구하기

반대로 친구 쌍이 최소가 되려면 참가자들을 각 팀에 최대한 균등하게 분배해야 합니다. 균등 분배 시 기본 인원과 남는 인원(나머지)을 고려하여 아래 공식으로 계산할 수 있습니다.

minPairs = m * (((n - m) / m + 1) * ((n - m) / m)) / 2 + ceil((n - m) / double(m)) * ((n - m) % m);

예제 코드

#include <iostream>
#include <cmath>
using namespace std;
void getPairs(int n, int m){
   int maxPairs = ((n - m + 1) * (n - m)) / 2;
   int minPairs = m * (((n - m) / m + 1) * ((n - m) / m)) / 2 + ceil((n - m) / double(m)) * ((n - m) % m);
   cout << "Minimum pairs = " << minPairs << "\n";
   cout << "Maximum pairs = " << maxPairs << "\n";
}
int main(){
   getPairs(3, 2);
   return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.

Minimum pairs = 1
Maximum pairs = 1

n = 3, m = 2인 경우 팀당 최소 한 명씩 배정해야 하므로 팀 구성은 반드시 2명 + 1명이 됩니다. 따라서 어떻게 배치하더라도 2명 팀에서 단 하나의 친구 쌍만 생기며, 최솟값과 최댓값이 모두 1이 되는 것입니다.