[Algospot] S@iNT 그룹 권회장의 스타크래프트 대회

문제 정보

문제ID

STARCRAFT

출제자

Taeyoon_Lee

출처

RUN Programming Contest, Spring 2009

시간제한

2000ms

메모리제한

65536kb

분류

.

문제 설명

단판 P%의 승률이 2K-1 판 K선 승제 일 경우 우승 확률을 구하는 문제입니다.

문제 풀이

확률문제네요. 경우의 수나 순열 등...
2K-1 판 중 K 승할 확률, K+1 승할 확률, .... 2K-1 승할 확률를 모두 더하면 됩니다.

이런 문제는 순서를 반대로 생각하는게 식을 표현하기가 간단하죠.

2K-1 승할 확률이란. 단일경기 승리 확률의 2K-1 제곱으로 구할 수 있습니다.
2K-2 승할 확률이란, 단일경기 승리 확률의 2K-2 제곱 곱하기 단일경기 패배할 확률 * 해당 조합이 만들어 질 수 있는 경우의 수 로 구할 수가 있습니다.

조합은 아래 공식으로 구할 수 가 있습니다. (참고 블로그)

이제 위 내용들을 조합해서 식으로 나타내면 아래와 같습니다.

Show Spoiler : 숨겨진 내용은 제가 이 문제를 해결한 핵심 내용으로 문제를 푸는데 대한 힌트가 될 수 있습니다. 숨겨진 내용을 보시고자 하는 분만 클릭하여 주시기 바랍니다.Close Spoiler

위에서 구한 식을 코딩으로 구현하기만 하면 문제가 해결 됩니다.
제곱은 pow 함수로 간단히 구할 수 있지만 조합은 for문을 사용해야하는 군요.
Σ 계산까지하면 이중 for문 즉, O(n²) 의 시간복잡도가 나옵니다.

이를 개선하기 위해서는 중복으로 사용할 수 있는 조합의 값을 선처리로 구해놓고 이를 재활용해 사용하면 O(n)의 시간복잡도로 문제를 해결할 수 있습니다.

== 소스보기 ==

여기서 한가지 더, 문제를 풀고나니 선승제라는 표현이 애매한 것이 있어 문제를 다시한번 풀어보았습니다.

제가 전개한 식은 중간에 승리를 했어도 2K-1 판까지 모두 끝냈을 경우를 기준으로 식을 풀고, 코딩을 하였는데요.

경기가 끝나지 않았어도 K승을 모두 끝내버린다면, 경기가 끝나는 경우도 있을 것 같네요.

즉, K 판 동안 K 승 한 경우. K+1 판 동안 K승 한 경우..... 2K-1 판 동안 K승한 경우를 구하였습니다.

식은 아래와 같습니다.

결과는.... 두 해결방법 모두 동일한 결과가 나오네요.
두 식을 비교해서 두 식이 같다는 것을 증명... 하고는 싶으나 제 전공은 수학이 아니므로 여기서 이만 정리하겠습니다.

== 소스보기 ==

첫번째 풀이 결과

#

458451

문제

STARCRAFT

언어

cpp

길이

483B

수행시간

3ms

결과

정답

제출일

2016-08-22

두번째 풀이 결과

#

459962

문제

STARCRAFT

언어

cpp

길이

504B

수행시간

4ms

결과

정답

제출일

2016-08-26