[수학] 헤이카카오(22353)(C++)

https://www.acmicpc.net/problem/22353

22353번: 헤이카카오

 

1. 문제 개요

 

이하는 헤이카카오를 상대로 끝말잇기를 가볍게 여러 판 플레이하고 통계를 냈다. 그 결과 끝말잇기를 한 판 하는 데에는 a분이 걸리며, 현재 자신이 이길 확률은 d%라는 사실을 알게 되었다. 이하는 자신의 승률에 실망하고 이제 집중해서 플레이를 하기로 했다. 이하가 집중하면 끝말잇기에서 패배할 때마다 경험이 쌓여 이길 확률이 이전에 비해 k%만큼 오른다. 만약 이렇게 증가한 확률이 100%를 넘게 되면, 이하는 다음 판부터는 반드시 승리한다.

이하는 헤이카카오를 한 번 이길 때까지 끝말잇기를 하려고 한다. 이하가 끝말잇기를 진행하는 시간의 기댓값을 구해 보자.

 

 

2. 입출력

 

 

 

3. 문제 풀이

 

확률변수의 기댓값을 구하는 과정을 직접 구현해보는 문제.

가위바위보를 진행할때마다 승률이 증가하므로 평범한 Geometric random rariable의 expectation을 구하는 방법으로는 구할 수 없다.

따라서 확률변수의 기댓값을 구하는 식인 E[X] = Σx*P(X=x)를 구현한다.

 

이때, 가위바위보를 이길 때까지 K판 하는 확률은 승률이 p일때 (1-p)^(K-1) * p이고, 매판 게임을 진행할때마다 승률이 증가하는 경우에는 (1-p)*(1-p')*(1-p'')*(1-p''')*...*(p'''''''')이 된다. 즉, 매 판마다 승률을 업데이트 해주어야한다.

 

따라서 이중 루프를 돌면서 P(X=1) ~ P(X=1000) 까지의 확률값을 모두 더해준다.

바깥 쪽 루프를 1000번 돌리면 통과되었고 100번 돌렸을 때는 통과되지 않았다.

 

 

4. 전체 코드

//
//  main.cpp
//  backjoon
//
//  Created by 배주현 on 2022/02/09.
//

#include <iostream>

using namespace std;

int main(void) {
    int a,d,k;
    scanf("%d%d%d",&a,&d,&k);
    
    double sum = 0;
    double p = (double)d/100;
    for(int i=1;i<1000;i++) {
        p = (double)d/100;
        double temp = 1.0;
        for(int j=1;j<i;j++) {
            temp *= (1-p);
            p += (p*(double)k/100);
            if(p>1) p=1;
        }
        sum += (i*temp*p);
    }

    printf("%f",a*sum);
}