[Python] 백준 1344: 축구

https://www.acmicpc.net/problem/1344

1344번: 축구

접근 방법

최대 18점을 낼 수 있으며, 적어도 한 팀이 소수로 득점할 확률은 1 - 두 팀이 소수로 득점하지 않을 확률과 같다.

부분집합을 만들고, 점수를 낼 경우 1로 만들고 내지 않을 경우 0으로 배치한다. 부분집합의 sum 값이 소수가 아닐 경우 percent 함수를 돌고자 했다. 여기서 percent 함수는 원하는 점수만큼 점수를 낼 때의 확률을 이야기한다. 

시간 초과가 날 가능성을 최대한 줄이기 위해서 딕셔너리를 만들고, 점수가 나올 경우의 수를 value값에 넣어주었다.

예를 들어 15분 경기를 하고, 1점을 얻는 것에 따른 딕셔너리는...

 

dic = {0:1, 1:3, 2:3, 3:1}이 된다! 확률을 구해준 후 value값을 곱해주어 시간을 최대한 줄이고자 했다.

 

ANS

# 최대 18점 득점 가능(5분당 1골, 90분 플레이)
# 0~16에서의 소수는 2, 3, 5, 7, 11, 13, 17
# 0~16에서의 소수가 아닌 수는 0,1,4,6,8,9,10,12,14,15,16,18
# 적어도 한 팀이 소수로 득점할 확률 = 1 - 두 팀이 소수로 득점하지 않을 확률

def percent(score, pct):
    cnt = 0
    while cnt != score: #점수를 낼 확률 구하기
        pct *= occur
        cnt += 1
    for i in range(18-score):
        pct *= notoccur
    return pct

def par(k):
    global dic
    if k == 18:
        if sum(res) not in PN: #소수가 아닌 경우
            dic[sum(res)] += 1
    else:
        res[k] = 0
        par(k+1)
        res[k] = 1
        par(k+1)

PN = [2, 3, 5, 7, 11, 13, 17]
percent_list = [0]*2
for a in range(2):
    dic = {0: 0, 1: 0, 4: 0, 6: 0, 8: 0, 9: 0, 10: 0, 12: 0, 14: 0, 15: 0, 16: 0, 18: 0}  # 경우의 수를 전부 정리

    occur = int(input())/100
    notoccur = 1 - occur
    res = [0] * 18
    par(0)

    for i in dic:
        dic[i] = percent(i,1) * dic[i] # 경우의 수 * 확률. 소수가 아닌 득점을 할 확률.
    percent_list[a] = sum(dic.values())

print(1-percent_list[0]*percent_list[1])