이 문제에서는 네 개의 값 p, q, r, s가 주어지며, 과녁을 맞힐 확률이 주어졌을 때 플레이어가 승리할 확률을 구하는 것이 과제입니다.
두 명의 플레이어가 양궁 게임을 진행하고 있습니다. 플레이어 1이 과녁을 명중시킬 확률은 p/q로, 플레이어 2가 과녁을 명중시킬 확률은 r/s로 정의됩니다. 우리가 구해야 할 것은 플레이어 1이 게임에서 승리할 확률입니다.
문제 이해를 위한 예시
입력
p = 3, q = 5, r = 2, s = 5
출력
0.789
풀이 접근 방법
이 접근 방식에는 확률에 대한 기본적인 지식이 필요합니다.
이 게임에서는 플레이어가 과녁을 쏠 기회를 얻는 횟수에 제한이 없습니다. 두 플레이어 모두 몇 번이든 화살을 쏠 수 있으므로, 승리 확률의 계산은 시도 횟수와 무관하게 이루어집니다.
먼저 각 플레이어의 명중 및 실패 확률을 정의해 보겠습니다.
- 플레이어 1이 과녁을 맞힐 확률: P1 = p/q → 빗나갈 확률은 1 − p/q
- 플레이어 2가 과녁을 맞힐 확률: P2 = r/s → 빗나갈 확률은 1 − r/s
무한 번의 시행에서 플레이어 1이 승리할 확률은 다음과 같이 전개됩니다.
win(P1) + lost(P1)·lost(P2)·win(P1)
+ lost(P1)·lost(P2)·lost(P1)·lost(P2)·win(P1) + ...
이를 수식으로 정리하면 다음과 같습니다.
P1 + (1−P1)(1−P2)·P1 + (1−P1)(1−P2)(1−P1)(1−P2)·P1 + ...
이것은 첫째 항 A와 공비 R을 가지는 무한 등비수열(GP)이며, 각 항은 다음과 같습니다.
A = P1
R = (1 − P1)(1 − P2)
R은 항상 1보다 작으므로, 무한 등비수열의 합 공식을 적용할 수 있습니다.
S = A / (1 − R)
따라서 플레이어 1의 최종 승리 확률 공식은 다음과 같이 유도됩니다.
S = (p/q) / [1 − (1 − p/q)(1 − r/s)]
이 공식이 성립하는 이유는 직관적으로 설명할 수 있습니다. 한 라운드에서 두 플레이어가 모두 빗나갈 확률은 (1−P1)(1−P2)이며, 이 경우에만 게임이 다음 라운드로 넘어갑니다. 즉, 플레이어 1이 최종적으로 승리할 확률은 '첫 라운드에서 이길 확률'을 '게임이 종료되지 않을 확률'로 나눈 값과 같습니다.
C++ 구현 예제
#include <iostream>
using namespace std;
double calcWinningPropP1(double p, double q, double r, double s){
return (p / q) / (1 - ((1 - (p/q)) * (1 - (r/s))));
}
int main() {
double p = 3, q = 5, r = 2, s = 5;
cout << "The probability of player 1 winning is " << calcWinningPropP1(p, q, r, s);
return 0;
}
출력 결과
The probability of player 1 winning is 0.789474
위 코드는 앞서 유도한 공식을 그대로 함수로 구현한 것입니다. 입력값 p=3, q=5, r=2, s=5를 대입하면 플레이어 1의 승리 확률은 약 0.789474, 즉 약 78.95%로 계산됩니다. 단순 산술 연산만 수행하므로 이 알고리즘의 시간 복잡도는 O(1)입니다.