dynamic programming 2

* 틀린 내용이 있을 시 지적 부탁드립니다.

문제는 더블릿 21 dynamic programming에 있는 playoff입니다.

문제 사이트 주소입니다.

http://183.106.113.109/30stair/playoff/playoff.php?pname=playoff

문제는 이렇습니다.

게임을 총 N판을 합니다.

그런데 A선수와 B선수가 N판을 다 하기 전에 게임이 끝납니다.

그랬을 경우 각 선수가 상금을 가져갈 확률을 구하면 됩니다.

예제에 나온 입력 4, 1, 0인 경우

총 4판에 A가 한판 이긴 상태입니다.

이후 A가 나머지 게임을 이길 확률을 보면

A가 이겼을 때 : O

B가 이겼을 때 : X

1판 2판 3판 4판 5판 6판 7판 8판

O     O    O    O

        X     O    O     O

        O     X     O     O

        O     O    X      O

        X      X     O    O    O

...

이런식으로 모든 경우의 수를 구하고 각 판마다 어느 한명이 이길 확률은 1/2입니다.

그럼

첫 줄은 

O     O    O    O     1/2 * 1/2 * 1/2 =1/8

        X     O    O     O   1/2 * 1/2 * 1/2 *1/2 = 1/16

...이 값을 모두 더하면

21/32가 나오게됩니다.

이 값이 A가 이길 확률이고 

B는 1에서 A가 이길 확률을 빼면 됩니다.

저 값들의 규칙을 찾아보면 

총 N번의 경기중에 A가 이긴 횟수를 뺀만큼을 A가 이기면 됩니다.

그리고 그 사이에 B가 이기지 않는 한에서 B가 이기는 경우를 추가해줍니다.

처음은 4판중 A가 1판 이겼고 A가 이길 3판중에 B는 한판도 이기지 못합니다.

두번째는 A가 이길 3판과 B가 한번 이길 확률이 3번 있습니다.

세번째는 B가 이길 확률이 2번 있습니다.

이를 콤비네이션을 이용해 해결 할 수 있습니다.

첫줄은 B가 0번 이길 경우로 하나의 경우가 있습니다.  1/2

두번째줄은 3C1로 3판중(마지막 판은 A가 이김) B가 이길 경우는 1번인데 총 3번의 경우가 있습니다.   

1/2 * 1/2 * 1/2  이런 경기가 3번이니 

전체 1/8 + 1/8 + 1/8

세번째줄은 4C2로 4판중 B가 이길 경우는 2번입니다.    

이런 경우마다 <B가 이겨도 되는 자리수>C<B가 이긴수>, 그리고 실제 전체 게임수 - A가 실제 이긴횟수만큼 1/2를 곱해주고전부 더해주면 저의 경우 double에 넣어주도록 해서 소수가 나왔습니다.

이 소수를 기약분수로 바꾸고 분자, 분모로 나누어 출력해주면 됩니다.