백준 1892번 가위바위보

문제 요약

두 사람이 가위바위보를 하는데 총 N번까지 진행할 때, 먼저 K번 이길 확률이다. K와 N의 범위는 최대 40이다.

풀이

먼저, K가 1일 때를 생각해보자. 한 번이라도 게임의 승패가 결정나면 그 순간 끝난다. 그렇기 때문에, 최대 N번까지 진행하기 위해서는 N-1번 연속으로 내리 비기다가, N번째에 이겨야 한다.

게임이 K번보다 많이 진행되기 위해서는 내가 지기도 하고, 비기기도 해야 가능하다는 것이다.

일단, $i$번 째 라운드에서 K번 이길 확률을 $f(i)$라고 하자. $i$번째까지 진행되면서 내가 질 수 있는 최대 횟수는 K-1번이다. 그리고 $i-1$번의 게임 중에서 $K-1$번을 이겼어야 하며, $i$번째 게임에서 이기는 것이다. 이를 식으로 나타내자

$$
f(i) = \frac{\binom{i-1}{K-1} \sum_{r=0}^{K-1} \binom{i-K}{r} \times \binom{i-K}{i-K-r}}{3^i}
$$

위 식에는 문제가 있는데 $i$가 2_K-1은 되어야 한다는 것이다. 생각해보면 총 게임 수가 2\_K-1일 때까지는 한번도 비기지 않아도 된다. 그러나 2*K일 때부터는 게임수가 저만큼 가려면 적어도 한번씩은 비겨야 한다. 그래서 게임수가 2*K-1 전일 때는 K-1번 이기고 나머지 게임은 비기거나 지면 된다. 그러면 $f$는 아래와 같다.

$$
f(i)=
\begin{cases}
0 \quad &(i \lt K) \\
\frac{\binom{i-1}{K-1} 2^{i-K}}{3^i} \quad &(K \le i \lt 2K-1) \\
\frac{\binom{i-1}{K-1} \sum_{r=0}^{K-1} \binom{i-K}{r} \times \binom{i-K}{i-K-r}}{3^i} \quad &(i \ge 2K-1)
\end{cases}
$$

이 확률을 구했으면 답은 $f(1)$부터 $f(N)$까지 합이다.

코드

숫자가 unsigned long long 범위까지 가야한다. 조심하자.

#include<bits/stdc++.h>
using namespace std;
using ll = unsigned long long;

ll gcd(ll a, ll b) {
    if (!b) return a;
    else return gcd(b, a % b);
}

struct Fraction {
    ll numerator, denominator;
    Fraction(ll _n, ll _d) : numerator(_n), denominator(_d) {
        ll g = gcd(numerator, denominator);
        numerator /= g; denominator /= g;
    };
    Fraction() {};
    Fraction operator*(Fraction rhs) {
        ll num = numerator * rhs.numerator;
        ll den = denominator * rhs.denominator;
        ll g = gcd(num, den);
        num /= g; den /= g;
        return Fraction(num, den);
    }
    Fraction operator+(Fraction rhs) {
        ll num, den, g, lcm;
        if (denominator == rhs.denominator) {
            num = numerator + rhs.numerator;
            den = denominator;
        }
        else {
            g = gcd(denominator, rhs.denominator);
            lcm = (denominator / g) * (rhs.denominator / g);
            lcm *= g;
            num = numerator * (lcm / denominator) + rhs.numerator * (lcm / rhs.denominator);
            den = lcm;
        }
        g = gcd(num, den);
        num /= g; den /= g;
        return Fraction(num, den);
    }
};
ll dp[555][555];
Fraction f[55];

ll comb(int n, int r) {
    ll& ret = dp[n][r];
    if (ret != 0) return ret;
    if (n == r || r == 0) return ret = 1;
    if (n <= 1) return ret = 1;
    return ret = comb(n - 1, r - 1) + comb(n - 1, r);
}

int main() {
    ll N, K; cin >> N >> K;
    ll pw = 1;
    for (int i = 1; i <= K; ++i) pw *= 3ULL;
    ll pw2 = 1;
    Fraction ans(1, pw);
    for (ll i = K; i < 2 * K - 1; ++i) {
        f[i] = Fraction(comb(i - 1, K - 1) * pw2, pw);
        pw *= 3ULL; pw2 *= 2ULL;
    }
    for (ll i = 2 * K - 1; i <= N; ++i) {
        ll sum = 0;
        for (ll x = 0; x < K; ++x) {
            sum += comb(i - K, x);
        }
        f[i] = Fraction(comb(i - 1, K - 1) * sum, pw);
        pw *= 3ULL;
    }
    for (int i = K + 1; i <= N; ++i) ans = ans + f[i];
    cout << ans.numerator << ' ' << ans.denominator << '\n';
    return 0;
}