C++로 해결하는 이상한 동전 던지기 문제

문제 설명

여러 개의 동전이 있다고 가정해 봅시다. i번째 동전을 던졌을 때 앞면이 나올 확률은 prob[i]입니다. 우리가 구해야 하는 것은 모든 동전을 정확히 한 번씩 던졌을 때, 앞면이 나온 동전의 개수가 target과 일치할 확률입니다.

예를 들어 prob 배열이 [0.5, 0.5, 0.5, 0.5, 0.5]이고 target이 0이라면, 다섯 개의 동전이 모두 뒷면이 나올 확률인 0.03125가 출력됩니다.

접근 방법

이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. dp[i][j]를 '처음 i+1개의 동전을 던졌을 때 정확히 j개의 앞면이 나올 확률'로 정의하면, 각 동전마다 앞면이 나오는 경우와 뒷면이 나오는 경우의 확률을 누적하여 답을 구할 수 있습니다.

해결 과정은 다음과 같습니다.

• n := prob 배열의 크기
• n × (target + 5) 크기의 2차원 배열 dp 생성
• 초기값 설정: dp[0,0] = 1 − prob[0], dp[0,1] = prob[0]
• i를 1부터 n−1까지 반복:
  • dp[i, 0] := (1 − prob[i]) * dp[i−1, 0]
  • j를 1부터 min(i+1, target)까지 반복:
    • dp[i, j] := (1 − prob[i]) * dp[i−1, j] + prob[i] * dp[i−1, j−1]
• dp[n−1, target] 반환

점화식의 의미를 살펴보면, i번째 동전에서 j개의 앞면이 나올 확률은 두 가지 경우의 합입니다. 첫째, i번째 동전이 뒷면(확률 1 − prob[i])이고 이전 동전들에서 이미 j개의 앞면이 나온 경우, 둘째, i번째 동전이 앞면(확률 prob[i])이고 이전 동전들에서 j−1개의 앞면이 나온 경우입니다.

다음 구현 예시를 통해 더 자세히 이해해 보겠습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   double probabilityOfHeads(vector<double>& prob, int target) {
      int n = prob.size();
      vector < vector <double> > dp(n, vector <double>(target+5));
      dp[0][0] = 1- prob[0];
      dp[0][1] = prob[0];
      for(int i =1;i<n;i++){
         dp[i][0] = (1-prob[i])*dp[i-1][0];
         for(int j =1;j<=min(i+1,target);j++){
            dp[i][j] = (1-prob[i])*dp[i-1][j] + prob[i]*dp[i-1][j-1];
         }
      }
      return dp[n-1][target];
   }
};
main(){
   vector<double> v = {0.5,0.5,0.5,0.5,0.5};
   Solution ob;
   cout << (ob.probabilityOfHeads(v, 0));
}

입력

[0.5,0.5,0.5,0.5,0.5]
0

출력

0.03125