주사위를 던져서 얻은 눈의 수의 합이 n이상이 되기 위해 던져야 하는 횟수의 기댓값

 13250번: 주사위 게임

 

1부터 6까지 6면 주사위를 1번 던져 나온 눈의 수만큼 사탕을 받는다고 하자.

 

사탕을 적어도 n개 이상 받기 위해 던져야하는 횟수의 기댓값은?

 

n = 1이면 1번만 던져도 사탕을 1개 이상 받으므로 1번

 

--------------------------------------------------------------------------------------------------------------------------------------

 

통계적?으로 접근할려고하면 굉장히 어렵다

 

확률변수 X를 먼저 정의하고

 

X = 사탕을 n개 이상 받기 위해 던져야하는 횟수

 

P(X = 1), P(X = 2), ...을 구한다음 xP(X = x)의 합을 구하면 될텐데

 

문제는 P(X = 1) 이런건 어떻게 구하냐 이거지

 

예를 들어 n = 1이면 P(X = 1)은 얼마임? 100%인가? 그러면 P(X = 2)는??

 

하루종일 고민했는데 모르겠더라고

 

다이나믹 프로그래밍으로 직관적으로 푸는게 있는데

 

합이 N이상이 되기 위해 던져야하는 횟수의 기댓값을 DP[N]으로 정의하면

 

DP[N] = 1 + (DP[N-1] + DP[N-2] + ... + DP[N-6])/6이다

 

N-1, N-2,...,N-6에서 주사위 1번을 던져야 N이 될 것이고 각각은 1/6의 확률로 등장하기 때문이라는데

 

직관적으로 맞긴한데

 

통계학과 자존심에 왜 되는지 고민해봤는데 합리적인 대답을 찾았다

 

'The Law of total expectation'이라는 법칙이 있다

 

E(X) = E(E(X|Y))

 

이 식은 바꿔쓰면 다음과 같다

 

E(X|Y = y)는 Y = y에 대한 확률변수이므로 $E( E(X|Y = y) ) = \sum_{y}^{} P(Y = y) E(X|Y = y) = E(X)$

 

X가 합이 적어도 N에 도달하기 위해 던져야하는 횟수라고 하자

 

주사위를 1번 던지는 사건 Y = y라고 정의하면 X | Y = y는 1번 던졌더니 주사위의 눈이 y일때 N에 도달하기 위한 횟수이므로

 

1 + (N - y에 도달하기 위한 횟수)와 같으니 $E(X) = \sum_{y}^{6} P(Y=y)E(X|Y=y)$에서

 

E(X)는 합이 적어도 N이상이기 위해 던져야하는 횟수 DP[N]

 

E(X|Y = y)는 합이 적어도 N - y이상이기 위해 던져야하는 횟수 DP[N-y]

 

P(Y = y) = 1/6이므로

 

$DP[N] = \sum_{y}^{6} 1/6*(1+DP[N-y]) = 1/6 * (6+DP[N-1] + DP[N-2] + ... + DP[N-6])$

 

따라서

 

$$DP[N] = 1 + (DP[N-1] + ... + DP[N-6])/6$$

 

 

 

 

n = int(input())

E = [0]*(n+1)

for i in range(1,n+1):
    
    v = 0

    for j in range(1,7):
        
        if i-j >= 0:

            v += E[i-j]
        
    E[i] = 1 + v/6

print(E[n])