[DP] 게임 이기기

DP 연습문제 : 게임 이기기

문제

두 친구 부커와 드윗이 재밌는 게임을 하고있습니다. 턴을 돌아가면서 가방에 있는 빨간공 또는 초록색 공을 꺼냅니다. 각 참가자는 돌아가면서 공을 꺼내고, 절대 다시 넣지 않습니다. 처음 빨간공을 꺼낸 사람이 이깁니다. 부커가 무조건 처음 시작합니다. 만약, 가방안에 아무 공이 없거나 꺼낼 빨간공이 없으면 부커가 이깁니다.

부커가 이길 확률은 어떻게 될까요?

예제

다음과 같은 입력을 받는다고 하겠습니다. 가장 처음 입력은 test case 입니다. 각 라인의 첫번째 숫자는 빨간 공의 갯수, 두번째 숫자는 초록색 공의 갯수 입니다.

3
2 1
1 1
10 0

출력값은 아래와 같습니다.

0.666667
0.500000
1.000000

첫번째 test case 는 빨간 공이 2개 그리고 초록색 공이 1개, 그러니까 빨간 공을 뽑을 수 있는 확률은 $\frac{2}{2+1} = 0.666667$ 입니다.

두번째 test case 는 빨간 공이 1개 그리고 초록색 공이 1개, 그러니까 빨간 공을 뽑을 수 있는 확률은 $\frac{1}{1+1} = 0.500000$ 입니다.

세번째 test case 는 빨간 공이 10개 그리고 초록색 공이 0개, 부커가 첫번째로 공을 뽑기 때문에 무조건 부커가 이기겠네요. 그렇기에 확률은 $\frac{10}{10+0} = 1.000000$ 입니다.

이렇게 쉬운 확률 문제에 DP 가 끼어들 자리가 있을까요?
문제를 먼저 풀어보세요.

---

정답

예를 들어 입력값이 999 999 가 됬다고 합시다. 너무 쉽습니다. 빨간공이 $999$ 개고, 초록색 공이 $999$ 개 이니까 확률은 $\frac{999}{999+999} = 0.500000$ 이네요. 과연 이것이 정답일까요?

틀린 답입니다. 이 게임은 번갈아가면서 진행하는 게임이므로, 부커가 맨 처음에 빨간공을 뽑지 못했을 확률도 생각을 해봐야 합니다. 다시말하면, 저희가 계산한 확률은 부커가 맨 처음에 빨간공을 뽑을 확률만 계산했다는 것이죠.

부커가 빨간공을 처음에 뽑지 못하면 어떻게 될까요? 부커가 빨간공을 뽑지 못하고 초록공을 뽑고, 드윗이 초록색 공을 뽑아야 합니다. 드윗이 빨간색 공을 뽑으면 부커가 게임을 지니까 이것은 고려대상이 아닙니다. 드윗이 초록색 공을 뽑은 다음에는 부커가 다시금 빨간공을 뽑으면 이제 부커가 이기는 게임이 됬으므로, 이 확률도 고려해 봐야겠죠?

그렇다면 위의 설명을 수식으로 표현하면 어떻게 될까요? 일단 문장으로 표현해보겠습니다.

부커가 빨간공을 뽑을 확률 + 부커가 초록색 공을 뽑을 확률 * 드윗이 초록색 공을 뽑을 확률 * 부커가 빨간색 공을 뽑을 확률 + 또 부커가 초록색 공을 뽑을 확률 ...

빨간색 공은 뽑기만하면 게임이 끝나버리니까, 확률 계산은 초록색 공을 기준으로 초록색 공이 바닥날때까지 계속해서 확률을 계산하면 되겠습니다. 수식으로 표현하면 다음과 같습니다.

$$\frac{R}{R+G} + \frac{G}{R+G} * \frac{G}{R+G-1} * \frac{R}{R+G-2} + \frac{G}{R+G-2} * \frac{G}{R+G-3} * \frac{R}{R+G-4} + \cdots$$

여기서 눈여겨봐야 할 점은 $\frac{R}{R+G}$ 이것과, $\frac{R}{R+G-2}$ 이것 입니다. 공의 갯수만 달라질뿐 서로 비슷한 형태죠? DP의 성질인 '중복되는 서브문제들'을 가지고 있네요. 즉, 전에 계산한 확률을 끌어다가 현재 확률 계산을 위해 써야겠습니다. $prob(R,G)$ 를 $R$ 개의 빨간 공, $G$ 개의 초록색 공이 가방에 들어있을때 부커가 이길 확률이라고 가정하겠습니다. 그렇다면 수식은 아래와 같습니다.

$$ prob(R,G) = \frac{R}{R+G} + \frac{G}{R+G} * \frac{G}{R+G-1} * prob(R,G-2) , G \geq 2$$

이것을 재귀 형식이 아닌 tabulation을 이용해서 bottom up 방식을 이용하겠습니다. $prob(R,G-2)$ 를 먼저 계산하고 $prob(R,G)$ 를 계산할때 $prob(R,G-2)$ 의 계산된 확률을 가져다 쓰는겁니다. 물론 $G = 0$ 일때 확률이 $1$ 이므로 $prob(R,0)$ 부터 $prob(R,G)$ 까지 거슬러 올라가야겠죠.

dp = [[-1] * 1001 for _ in range(1001)]

# 뽑을공이 없거나 빨간공이 하나도 없을 경우
# 빨간공만 있을 경우는 부커가 무조건 이깁니다.
for i in range(1001):
    dp[i][0] = 1
    dp[0][i] = 1
dp[0][0] = 1

# tabulation 을 이용한 bottom up 방식을 사용했습니다.
def repeat(r,g):
    if dp[r][g] != -1 :
        return dp[r][g]

    for i in range(1, 1001):
        if i == 1:
            dp[r][i] = r/(r+i)
        else :
            dp[r][i] = r/(r+i) + i/(r+i) * (i-1)/(r+i-1) * dp[r][i-2]
    return dp[r][g]

# 알고리즘을 테스트 하기위한 드라이버 프로그램
T = int(input())
for _ in range(T):
    r,g = list(map(int, input().strip().split(" ")))
    ans = repeat(r,g)
    print (format(ans, '.6f'))

---

분명 문제의 난이도는 매우 쉬움으로 적혀있었는데, 저는 푸는데 왜이렇게 오래걸렸는지..ㅎ