백준 : 6494번, Another lottery

문제 주소 : https://www.acmicpc.net/problem/6494

정답 비율 : 68.421% (2021.12.19 22:16 기준)

6494번: Another lottery

 

<< 문제 요약 >>

1. n명이 각각 1 ~ m 회차 m개의 로또를 구매합니다.

2. 각 회차의 당첨자는 해당 회차에서 판매된 모든 티켓을 동일한 확률로 무작위로 하나를 선택하여 해당 티켓의 주인이 로또에 당첨됩니다.

3. i번째(1 ≤ i ≤ m) 회차의 상금은 2^i dollor이 됩니다.

4. 이때 각 사람이 다른 사람보다 더 많은 상금을 받을 확률을 구하시오.

 

<< 문제 풀이 >>

간단한 수학 문제입니다.

1 ~ i번째 회차에서 당첨되어 얻는 상금의 합은 i + 1번째 회차에서 얻는 상금보다 적습니다.

따라서 m회차(마지막 회차)에서 당첨할 확률이 다른 사람보다 더 많은 상금을 받을 확률이 되겠습니다.

 

<< Python3 코드 >>

import sys
sys.setrecursionlimit(100000)


def GCD(num1, num2):
    if num1 % num2 == 0:
        return num2
    else:
        return GCD(num2, num1 % num2)


while True:
    A, B = list(map(int, input().split()))

    if A == B == 0:
        break

    lastLottery = [int(sys.stdin.readline().split()[-1]) for a in range(A)]
    total = sum(lastLottery)
    str_list = []
    for num in lastLottery:
        gcd = GCD(num, total)
        str_list += [str(num // gcd), " / ", str(total // gcd), "\n"]

    sys.stdout.write(''.join(str_list), end='')