[Python] 32612번 Expected Eyes

 

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

---

 

24/11/15

 

 

두 가지 방법으로 풀 수 있다. 둘다 소개해보려고 한다.

---

 

문제 접근 방식:

 

 

1. 파이썬의 itertools모듈의 product함수를 이용한다.

 

직접 모든 가능한 경우의 수를 조사하면서 기댓값을 구한다. 이 접근방식의 시복도는 최대 $\mathcal{O}(8^8)$이다. 따라서 파이썬3로는 통과하기 힘들고 파이파이로 하면 통과된다.

 

2. 기댓값의 선형성 이용

 

전체 기댓값은 선형성에 의해 각 주사위의 기댓값의 합과 같다. 이를 이용하면 한줄로 코딩할 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 32612번 Expected Eyes
# 1. 나이브한 반복 풀이
from itertools import product
n = int(input())
x = list(map(int, input().split()))
m, k = 0, 0
for tpl in product(range(1, 9), repeat = n):
    flag = False
    for i in range(n):
        if tpl[i] > x[i]:
            flag = True
            break
    if flag: continue
    k += 1
    m += sum(tpl)
print(m/k)
# 2. 기댓값의 선형성
input()
print(sum(map(lambda x:(int(x)+1)/2,input().split())))