[백준 22353] 헤이카카오 (C++)

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

문제

---

일상을 바꾸는 단어, 헤이카카오는 카카오엔터프라이즈의 인공지능 플랫폼 Kakao i에 기반한 인공지능 비서 어플리케이션이다. 헤이카카오를 사용하면 음악 검색, 길 찾기, 외국어 번역 등 다양한 기능들을 말 한 마디로 이용할 수 있다.

2020 헤이카카오 연말 결산에 따르면, 헤이카카오가 "고마워", "안녕" 다음으로 많이 들은 말은 "끝말잇기 하자"였다고 한다. 방에서 핸드폰을 만지작거리던 이하도 심심풀이로 헤이카카오와 끝말잇기를 해 보기로 했다.

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

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

입력

---

첫 번째 줄에는 세 개의 정수 a,d,k가 공백으로 구분되어 주어진다. (1≤a,d,k≤100) 이는 끝말잇기 한 판에 a분이 걸리며 집중을 시작한 이하가 처음에 끝말잇기에서 이길 확률이 d%이고 패배할 때마다 승률이 이전에 비해 k%만큼 오름을 의미한다.

입력으로 주어지는 값은 모두 정수이다.

 

출력

---

이하가 이길 때까지 끝말잇기를 진행하는 시간의 기댓값을 분 단위로 출력한다. 절대오차 또는 상대오차가 10−6 이하면 정답으로 인정된다.

 

문제 풀이

---

수학 문제.

 

i번째 끝말 잇기에서 이기려면 이전까지 패배 확률을 모두 곱한 확률에 현재 판의 승률을 곱해주면 된다. 이를 이용하여 승률이 100%가 될 때까지 기댓값을 구해주면 된다. 현재 판의 우승 확률과 여태까지의 패배 확률을 모두 곱한 확률을 저장하는 변수와, 여태까지의 기댓값을 저장하는 변수를 만들어준다. 처음에는 우승 확률이 d이고, 첫번째 판에서 우승 시 얻어지는 기댓값은 d이다. 이후 100%가 될 때까지 이전 판의 패배 확률, 현재 판의 우승 확률을 곱해주며 기댓값을 계산해주면 된다. 

 

아래는 코드.

#include <iostream>
using namespace std;

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

	double a, d, k;
	cin >> a >> d >> k;
	double currentWin = d / 100;
	double currentDefeat = 1;
	double count = 1;
	double answer = (count * a) * currentDefeat * currentWin;
	while (currentWin != 1)
	{
		currentDefeat *= 1 - currentWin;
		currentWin += currentWin * k / 100;
		if (currentWin >= 1)
		{
			currentWin = 1;
		}
		count++;
		answer += (count * a) * currentDefeat * currentWin;
	}
	cout << fixed;
	cout.precision(7);
	cout << answer << "\n";
	return 0;
}