C++로 M면 주사위를 N번 던졌을 때 최댓값의 기댓값 계산하기

문제 개요

이 글에서는 M개의 면을 가진 주사위를 N번 던졌을 때, 기대할 수 있는 최대 점수, 즉 최댓값의 기댓값을 계산하는 방법을 다룹니다.

주사위의 첫 번째 면에는 1개의 점, 두 번째 면에는 2개의 점이 있으며, 이런 식으로 M번째 면에는 M개의 점이 있습니다. 각 면이 나올 확률은 모두 동일하게 1/M입니다.

예제로 이해하기

입력 − M=2, N=3

출력 − 1.875

설명 − 주사위는 2개의 면 {1, 2}를 가집니다.

주사위를 3번 던지면 표본 공간의 크기는 M^N = 2³ = 8이 됩니다.

{(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2),
(2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)}
(1, 1, 1)의 최댓값 = 1
(1, 1, 2)의 최댓값 = 2
(1, 2, 1)의 최댓값 = 2
(1, 2, 2)의 최댓값 = 2
(2, 1, 1)의 최댓값 = 2
(2, 1, 2)의 최댓값 = 2
(2, 2, 1)의 최댓값 = 2
(2, 2, 2)의 최댓값 = 2
각 경우의 확률 = 1/23 = 0.125
따라서 최댓값의 기댓값 = (1+2+2+2+2+2+2+2) × 0.125 = 1.875

또 다른 예로, 입력 − M=2, N=2일 때 출력은 1.75가 됩니다.

접근 방법

• 특정 숫자 i가 최댓값으로 나올 수 있는 경우의 수는 바로 이전 숫자를 활용한 공식 i^N − (i−1)^N으로 구할 수 있습니다.

  예를 들어 M=4, N=2일 때, 최댓값이 4가 되는 경우의 수는 4² − (4−1)² = 7입니다.

  따라서 최종 답은 1부터 M까지의 모든 i에 대해 (i × (i^N − (i−1)^N)) / M^N을 계산한 뒤, 이 값을 모두 더한 것입니다.

• MaxExpect() 함수에서는 합계를 저장할 double형 변수 max = 0을 초기화합니다.

• 그런 다음 i=M부터 시작해 i가 0보다 클 때까지 반복문을 실행합니다.

• 반복문 안에서 위에서 설명한 공식을 적용하고, 계산된 결과값을 모두 변수 max에 더해갑니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
double MaxExpect(double M, double N){
   double max = 0.0, i;
   for (i = M; i; i--)
      /* 최댓값을 구하고
      최댓값들의 합을 계산하는 공식 */
      max += (pow(i / M, N) - pow((i - 1) / M, N)) * i;
      return max;
}
int main(){
   double M = 2, N = 3;
   cout << MaxExpect(M, N);
   return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다 −

1.875