C++로 N개의 컨테이너에서 X를 뽑을 확률 최대화하기

확률 계산의 기본 공식

확률은 일반적으로 다음과 같이 정의됩니다.

Pi = (유리한 결과의 수) / (전체 결과의 수)

문제 이해하기

컨테이너의 개수를 나타내는 숫자 N이 주어지고, 두 숫자 X와 Y의 복사본이 각각 N개씩 있습니다. 목표는 X의 복사본들을 N개의 컨테이너에 분배하여, 임의의 컨테이너에서 X를 뽑을 확률을 최대화하는 것입니다.

위 공식에서 알 수 있듯이 확률 Pi를 높이려면 분자(유리한 결과의 수)를 늘리거나 분모(전체 결과의 수)를 줄여야 합니다. 이를 위해 가장 효과적인 배치 전략은 단 하나의 컨테이너에만 Y의 복사본을 몰아 넣고, 모든 컨테이너에는 X의 복사본을 최소 1개씩 담는 것입니다.

앞의 N-1개 컨테이너에는 X 복사본을 1개씩만 담습니다.
마지막 1개의 컨테이너에는 X 복사본 1개와 Y 복사본 N개를 모두 담습니다.

이렇게 배치하면 앞의 N-1개 컨테이너에서는 반드시 X가 나오고(확률 1), 실패 가능성은 마지막 컨테이너에만 존재하게 됩니다.

수학적 유도

앞의 (N-1)개 컨테이너에서 X를 뽑을 확률은 다음과 같습니다.

P_N-1 = 1

마지막 컨테이너에는 X 1개와 Y N개, 즉 총 N+1개의 아이템이 있으므로 여기서 X를 뽑을 확률은 다음과 같습니다.

P_N = 1/(N+1)

각 컨테이너가 선택될 확률이 동일하다고 가정하면, 전체 확률 Pm은 가중 평균으로 계산되며 최종적으로 다음과 같이 정리됩니다.

Pm = [(N-1)/N] × 1 + [1/N] × [1/(N+1)]
∴ Pm = N / (N + 1)

입출력 예시

입력 − N = 1
출력 − N=1일 때 최대 확률은 0.5
설명 − 컨테이너가 1개뿐이고 그 안에 X와 Y가 각각 1개씩 들어 있으므로, X를 뽑을 확률은 1/2 = 0.5입니다.

입력 − N = 3
출력 − N=3일 때 최대 확률은 0.75
설명 − 세 컨테이너 모두 X 복사본을 1개씩 가지고 있으며, 마지막 컨테이너에는 Y 복사본 3개가 함께 들어 있습니다. 따라서 최대 확률은 3/4 = 0.75입니다.

알고리즘 접근 방법

컨테이너의 개수 N을 정수 값으로 입력받습니다.
X를 뽑을 최대 확률을 저장할 변수 maxP를 선언합니다.
주어진 N에 대해 maxP = N/(N+1) 공식으로 계산합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
int main(){
   int N = 3;
   double maxP = (double)N / (N + 1);
   cout << "Maximum Probability for N = " << N << " is, " << maxP << endl;
   return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Maximum Probability for N = 3 is, 0.75

복잡도 분석

이 알고리즘은 단순히 공식을 한 번 적용해 결과를 구하므로 시간 복잡도와 공간 복잡도 모두 O(1)입니다. N이 아무리 커져도 즉시 답을 계산할 수 있다는 점이 이 접근 방식의 가장 큰 장점입니다.