AtCoder Educational DP Contest J - Sushi 분석

https://atcoder.jp/contests/dp/tasks/dp_j

J - Sushi

 

앳코더에는 Educational DP Contest라고 PS에서 자주 출몰하는 26가지 유형을 정리한 DP 문제집이 제공되고 있다. 그중에서도 J는 기댓값을 다루는데 어떻게 푸는지 본인의 시행착오를 덧붙여 분석하고자 한다.

 

먼저 삼소멤 블로그에서는 다음과 같이 설명하고 있다.

 

 

다 좋은데 기댓값이 $\frac{N - (i + j + k)}{i + j + k}$ 라고 한다. 하지만 기하 분포의 기댓값을 검색하면 $\frac{1}{p}$이라는 식만 나와 어떻게 되는 건지 이해가 잘 안 된다.

 

근데 이건 멍청한 발언이었고 $p$는 확률 그 자체라는 사실을 기억하자. 초밥이 들어있는 접시를 고를 확률 $p$를 구해야 한다고 하면 $p = \frac{i + j + k}{N}$이다.

 

즉, 초밥이 있는 접시를 고르기 위해 시도하는 횟수의 기댓값은 $\frac{1}{p} = \frac{N}{i + j + k}$이다.

 

아니 그래도 설명에 쓰여있는 식과 다르지 않는가? 사실 이건 $E(X)$와 $E(Y)$중 어디를 보느냐의 차이다. 여기서 X는 실패 횟수, Y는 시행 횟수이다. 그리고 다음 식이 성립한다고 한다.

 

$E(Y) = E(X + 1) = \frac{1}{p}$

 

즉, 우리가 위에 구한 건 초밥을 성공적으로 먹기 위한 시행 횟수의 기댓값을 구했다는 것을 알 수 있다.

 

근데 우리는 초밥을 먹는 걸 성공하면 dp 재귀를 또 수행해야 하므로 $E(Y)$를 구하면 안 된다. $E(X)$를 구해야 하는데 이건 어떻게 구할까? 바로 $E(X) = \frac{1 - p}{p}$라고 한다.

 

위 식대로 하면 설명에 써진 기댓값 $\frac{N - (i + j + k)}{i + j + k}$을 유도할 수 있다.

 

그러면 이제 남은 거는 우항에 있는 3가지 dp 전개를 수행하기만 하면 된다.

 

하지만 설명의 점화식에 빠진 부분이 있다. 재귀를 들어갈 때마다 1을 더해주는 걸 잊지 말아야 한다. 그도 그럴게 횟수의 기댓값을 구하는 건데 그 횟수를 추가하지 않는다는 건 무척이나 이상하다.

 

위 요소들을 고려하면 다음과 같은 구현을 할 수 있게 된다.

 

https://atcoder.jp/contests/dp/submissions/35610571

 

쓰고 보니 내가 너무 바보 같다. 자고 일어나면 기댓값 dp 문제집이나 풀어야겠다.