이 문제는 간단히 말하자면 사용자가 인공지능을 한 번 이길 때까지 끝말잇기를 했을 때, 끝말잇기를 진행한 시간의 기댓값을 구하는 문제입니다. 예를 들어 한 판당 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;// 자리값 맞춰서 출력
}
C++
복사