백준 22353번: 헤이카카오

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

22353번: 헤이카카오

 

이 문제는 간단히 말하자면 사용자가 인공지능을 한 번 이길 때까지 끝말잇기를 했을 때, 끝말잇기를 진행한 시간의 기댓값을 구하는 문제입니다. 예를 들어 한 판당 1분이 걸리는 끝말잇기에서 첫 판에서 이길 확률이 50%이고 현재 판에서 졌을 시 다음 판에서 이길 확률이 이전에 비해 50% 오르는 경우가 있다고 합시다. 이 경우 끝말잇기를 진행하는 시간의 기댓값을 구하기 위해 아래와 같은 계산 과정을 거쳤습니다.

먼저 각 판을 이길 확률 d를 구했습니다.

 

첫 번째 판을 이길 확률은 문제에서 제시된 첫 판을 이길 확률을 그대로 사용해 50% 즉, 50/100입니다. 여기서 50%를 분수 형태로 사용한 이유는 백분율을 곱셈식에서 활용할 땐 %를 없애고 분수 꼴로 바꿔줘야 하기 때문입니다.

 

두 번째 판을 이길 확률은 전 판을 이길 확률보다 50% 증가하므로 전판의 확률에 전판 확률의 50%를 더해주었습니다.

 

세 번째 판을 이길 확률 역시 전 판을 이길 확률보다 50% 증가하므로 전판의 확률인 75%에 75%의 50%를 더해주었습니다. 이 경우 증가한 확률이 100%를 넘게 된 경우로 다음 판부턴 반드시 승리하므로 더 이상 계산할 필요가 없습니다.

 

첫 판을 이길 확률을 d1, 두 번째 판을 이길 확률을 d2, 세 번째 판을 이길 확률을 d3로 두었을 때 해당 판을 이길 확률인 d에 대한 관계식을 얻을 수 있었습니다.

 

다음으로 해당 판에서 게임이 끝날 확률을 구했습니다. 해당 판에서 게임이 끝날 확률은 이전 판들을 모두 질 확률 prev와 현재 판을 이길 확률 d를 곱해주어 구했습니다. prev도 d와 마찬가지로 관계식을 구해주었습니다.

 

마지막으로, 끝말잇기를 진행하는 시간의 기댓값

= 첫 번째 판에서 게임이 끝날 확률 * 걸린 시간

+ 두 번째 판에서 게임이 끝날 확률 * 걸린 시간

+ 세 번째 판에서 게임이 끝날 확률 * 걸린시간

이라는 걸 표를 통해 알 수 있었습니다.

 

지금까지 말한 것들을 코드에 나타낸 바를 살펴보면 먼저 백분율 형태로 주어진 것들은 100으로 나누어 분수 형태로 바꿔주었습니다. 여기서 d는 현재 판에서 이길 확률을, k는 현재 판을 패배했을 때 다음 판에서 승률이 오르는 비율을 의미합니다. 다음으로 while문을 통해 현재 판을 이길 확률이 100%가 될 때까지 게임을 반복하는 기능을 구현했습니다. 위에 그림으로 정리하며 구한 prev와 d에 대한 관계식을 이용해 반복문 안에서 각 판마다 게임이 끝날 확률을 구했고 이를 통해 끝말잇기를 진행하는 시간의 기댓값을 구했습니다. 이 값을 자릿수를 맞춰 출력해주었습니다.

#include<iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    double a;       //한 판당 걸리는 시간
    double d;       //현재 판에서 이길 확률
    double k;       //현재 판을 패배했을 때 다음 판에서 승률이 오르는 비율

    cin >> a >> d >> k;

    d /= 100;       //예를 들어 50%인 경우 계산 시 50/100으로 이용하므로
    k /= 100;       //백분율을 계산에서 사용하기 위해 분수 형태로 바꿔준다.

    double answer = 0;     //이길 때까지 끝말잇기를 진행하는 시간의 기댓값
    double prev = 1;       //이전 판들을 모두 졌을 확률
    int i = 1;             //끝말잇기 판수

    //현재 판까지 끝말잇기를 진행하는 시간의 기댓값 구하기
    while (1)
    {
        answer += i * a * prev * d;     //판수*한 판당 시간*이전 판들은 모두 졌을 확률*이번 판은 이겼을 확률
        i++;        //끝말잇기 판수 1 증가

        if (d == 1)     //현재 판을 이길 확률이 100%를 넘게 되면 다음 판부터는 반드시 승리하므로
            break;      //반복문 탈출

        prev = prev * (1 - d);   //이전 판들은 모두 진 확률
        d += d * k;              //현재 판은 이길 확률

        if (d >= 1)     //현재 판을 이길 확률이 100%를 넘게 되면
            d = 1;      //100%로 조정
    }

    cout.precision(7);
    cout << fixed << answer;    // 자리값 맞춰서 출력 
}