C++로 모든 문제를 배포하는 데 필요한 최소 메일 수 구하기

문제 설명

시험에 N개의 문제가 있고, 학급에는 총 K명의 학생이 있습니다. 이 가운데 N명의 학생은 각자 정확히 한 문제씩만 알고 있으며, 한 통의 메일에는 최대 X개의 문제까지 담을 수 있습니다.

목표는 학급의 모든 학생이 N개의 문제 전부를 알게 만드는 것이며, 이때 필요한 최소 메일 수를 구하는 것입니다.

예를 들어 N = 3, K = 3, X = 1인 경우 총 6통의 메일이 필요합니다.

• 학생 1이 자신의 문제를 학생 2와 학생 3에게 보냅니다 (2통).
• 학생 2와 학생 3도 마찬가지로 자신의 문제를 나머지 학생들에게 보내므로, 총 메일 수는 2 × 3 = 6통이 됩니다.

알고리즘

최종 정답은 아래 공식으로 계산할 수 있습니다.

ceil(N/X) * (K-N) + (ceil((N-1)/X) * (N-1)) + (N-1)

공식을 단계별로 살펴보면 다음과 같습니다.

• ceil(N/X) × (K−N) : 문제를 모르는 나머지 (K−N)명의 학생에게 N개의 문제를 모두 전달해야 하므로, 한 사람당 최소 ceil(N/X)통의 메일이 필요합니다.
• (N−1) + ceil((N−1)/X) × (N−1) : 처음부터 문제를 알고 있는 N명의 학생들이 서로의 문제를 주고받으며 모든 정보를 공유하는 데 필요한 메일 수입니다.

여기서 ceil()은 올림 함수로, 메일 하나에 담을 수 있는 최대 문제 수를 초과하지 않으면서 필요한 메일 통수를 계산할 때 사용됩니다.

C++ 구현 예제

#include <iostream>
#include <cmath>
using namespace std;

// 필요한 최소 메일 수를 계산하는 함수
int minMailsToBeSent(int n, int k, int x){
    int m = (n - 1) + ceil((n - 1) * 1.0 / x) * (n - 1) + ceil(n * 1.0 / x) * (k - n);
    return m;
}

int main(){
    int questions = 3; // 문제 수
    int students = 3; // 학생 수
    int X = 1; // 메일당 최대 문제 수
    cout << "보내야 하는 메일 수: " << minMailsToBeSent(questions, students, X) << endl;
    return 0;
}

실행 결과

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

보내야 하는 메일 수: 6

이처럼 올림 연산을 활용한 간단한 수식만으로도 모든 학생에게 문제를 전파하는 데 필요한 최소 메일 수를 효율적으로 계산할 수 있습니다.