BOJ 13686 - Vampiros 링크
(2024.04.18 기준 P3)

문제

플레이어 $1$의 생명력 $EV1$, 플레이어 $2$의 생명력 $EV2$ 그리고 $AT$, $D$가 주어진다. 플레이어 $1$과 플레이어 $2$의 전투는 매 턴마다 주사위를 굴려 진행한다. 주사위는 $1$부터 $6$까지 적힌 육면 주사위이며, 각 면이 나올 확률은 같다.
주사위를 굴려 나온 수가 $AT$보다 같거나 낮으면, 플레이어 $1$은 $D$만큼 생명력을 얻고 플레이어 $2$는 $D$만큼 생명력을 잃는다.
반대로 주사위를 굴려 나온 수가 $AT$보다 높으면, 플레이어 $1$은 $D$만큼 생명력을 잃고 플레이어 $2$는 $D$만큼 생명력을 얻는다.
이 전투는 두 플레이어 중 생명력이 $0$ 이하가 될 때까지 진행된다.

$EV1$, $EV2$, $AT$, $D$가 주어질 때, 플레이어 $1$이 이길 확률 출력

알고리즘

간단한 확률론을 이용한 dp. 그리고 최적화

풀이

일단 생명력과 생명력의 증감을 축소시켜보자.
$EV1$, $EV2$를 $D$로 나눠 올림한 정수를 각각 $A$, $B$라고 하자. $EV1$, $EV2$ 대신 $A$, $B$를 사용한다면, $D$가 아닌 $1$이 증감되는 전투로 수치를 축소시킬 수 있다.

$dp(r, A, B, C, a, b)$를 $AT = C$인 게임의 $r$번째 라운드에서 각 플레이어의 $A$, $B$가 각각 $a$, $b$인 상태인 확률이라고 하자. $w$를 플레이어 $1$이 이길 확률, $l$을 플레이어 $1$이 질 확률이라고 한다면 점화식은 다음과 같다.
$dp(r+1, A, B, C, a, b) = dp(r, A, B, C, a-1, b+1) \times w + dp(r, A, B, C, a+1, b-1) \times l$
이때 a와 b의 합은 A+B를 유지해야 한다.
또한 우항의 dp 식에서의 $a$나 $b$의 위치인 변수가 $0$이면 불가능하다. 이미 게임이 끝난 상태이기 때문이다.

이기고 지고 이기고 지고를 영원히 반복할 수 있다. 이 확률은 반복하면 반복할 수록 $0$에 수렴한다. 그래서 우리는 위 dp를 적당히 반복해줘야 한다. $1\,000$번 정도만 반복하니 AC를 받았다. 그런데 1000개의 공간을 그대로 잡으면 공간복잡도가 너무 늘어난다. 그래서 최적화가 필요하다.

점화식을 잘 보면 $r+1$번째 라운드로 넘어가면 $r$번째 라운드의 상태는 필요가 없어진다. 그러므로 $r$번째 라운드의 상태는 초기화해도 무방하다는 것이다.
그러므로 홀짝에 따른 받는 상태, 넘겨주는 상태 이렇게 두 공간만 설정해주면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

/* EV1, EV2를 D로 나눠 올림한 정수를 각각 A, B라고 하자.
각 플레이어의 A나 B가 0이 되면 더이상 게임이 진행되지 않는다.
dp(r, A, B, C, a, b)를 AT = C인 게임의 r번째 라운드에서 각 플레이어의 A, B가 각각 a, b인 상태인 확률이라고 하자.
w를 플레이어 1이 이길 확률, l을 플레이어 1이 질 확률이라고 한다면
점화식은 dp(r+1, A, B, C, a, b) = dp(r, A, B, C, a-1, b+1) * w + dp(r, A, B, C, a+1, b-1) * l이 된다.
이때 a와 b의 합은 A+B를 유지해야 한다.
또한 우항의 dp식에서 a나 b가 0이면 불가능하다. 이미 게임이 끝난 상태이기 때문이다.

위 dp를 적당히 1000번 정도만 반복하면 되는데, 1000개의 공간을 잡으면 공간복잡도가 너무 늘어난다.
점화식을 잘 보면 r+1로 넘어가면 r의 상태는 필요가 없어진다.
이는 즉 받는 상태, 넘겨주는 상태 이렇게 두 공간만 필요하다는 뜻이다. */

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    double dp[2][11][11][6][21][21], ans[11][11][6];
    memset(dp, 0, sizeof(dp)); memset(ans, 0, sizeof(ans));
    for (int A = 1; A <= 10; A++) for (int B = 1; B <= 10; B++) for (int C = 1; C <= 5; C++){
        double w = (double)C / 6, l = (double)(6 - C) / 6;

        dp[0][A][B][C][A][B] = 100;
        for (int r = 0, r_; r < 1000; r++){
            r_ = r & 1;
            for (int a = 0, b = A + B; a <= A + B; a++, b--) if (a && b){
                dp[r_ ^ 1][A][B][C][a + 1][b - 1] += dp[r_][A][B][C][a][b] * w;
                dp[r_ ^ 1][A][B][C][a - 1][b + 1] += dp[r_][A][B][C][a][b] * l;
            }

            // 현재 라운드에서 플레이어 1이 이긴 확률을 더해준다.
            ans[A][B][C] += dp[r_ ^ 1][A][B][C][A + B][0];

            // 상태를 다시 받기 위해 0으로 초기화
            for (int a = 0, b = A + B; a <= A + B; a++, b--) dp[r_][A][B][C][a][b] = 0;
        }
    }

    int EV1, EV2, A, B, C, D;
    cout << fixed;
    cout.precision(1);
    while (true){
        cin >> EV1 >> EV2 >> C >> D;
        if (!EV1) break;

        A = ceil((float)EV1 / D);
        B = ceil((float)EV2 / D);
        cout << ans[A][B][C] << '\n';
    }
}

• Python

import sys; input = sys.stdin.readline
from math import ceil

''' EV1, EV2를 D로 나눠 올림한 정수를 각각 A, B라고 하자.
각 플레이어의 A나 B가 0이 되면 더이상 게임이 진행되지 않는다.
dp(r, A, B, C, a, b)를 AT = C인 게임의 r번째 라운드에서 각 플레이어의 A, B가 각각 a, b인 상태인 확률이라고 하자.
w를 플레이어 1이 이길 확률, l을 플레이어 1이 질 확률이라고 한다면
점화식은 dp(r+1, A, B, C, a, b) = dp(r, A, B, C, a-1, b+1) * w + dp(r, A, B, C, a+1, b-1) * l이 된다.
이때 a와 b의 합은 A+B를 유지해야 한다.
또한 우항의 dp식에서 a나 b가 0이면 불가능하다. 이미 게임이 끝난 상태이기 때문이다.

위 dp를 적당히 1000번 정도만 반복하면 되는데, 1000개의 공간을 잡으면 공간복잡도가 너무 늘어난다.
점화식을 잘 보면 r+1로 넘어가면 r의 상태는 필요가 없어진다.
이는 즉 받는 상태, 넘겨주는 상태 이렇게 두 공간만 필요하다는 뜻이다. '''

dp = [[[[[[0] * (hp1 + hp2 + 1) for _ in range(hp1 + hp2 + 1)] for _ in range(6)] for hp2 in range(11)] for hp1 in range(11)] for r in range(2)]
ans = [[[0] * 6 for _ in range(11)] for _ in range(11)]
for A in range(1, 11):
    for B in range(1, 11):
        for C in range(1, 6):
            w = C / 6
            l = (6 - C) / 6

            dp[0][A][B][C][A][B] = 100
            for r in range(1000):
                r = r & 1
                for a in range(A + B + 1):
                    b = A + B - a
                    if a and b:
                        dp[r ^ 1][A][B][C][a + 1][b - 1] += dp[r][A][B][C][a][b] * w
                        dp[r ^ 1][A][B][C][a - 1][b + 1] += dp[r][A][B][C][a][b] * l

                # 현재 라운드에서 플레이어 1이 이긴 확률을 더해준다.
                ans[A][B][C] += dp[r ^ 1][A][B][C][A + B][0]

                # 상태를 다시 받기 위해 0으로 초기화
                for a in range(A + B + 1):
                    b = A + B - a
                    dp[r][A][B][C][a][b] = 0

while True:
    EV1, EV2, C, D = map(int, input().split())
    if not EV1:
        break

    A = ceil(EV1 / D)
    B = ceil(EV2 / D)
    print(format(ans[A][B][C], '.1f'))