[C++] 복권 (백준 1359번)

https://www.acmicpc.net/problem/1359

 

#include <iostream>
#include <vector>
using namespace std;

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

    long long f[11];
    f[0] = 1;
    for (int i = 1; i < 11; i++) f[i] = f[i - 1] * i;

    int n, m, k;
    cin >> n >> m >> k;

    cout.precision(10);
    int ans = 0;

    for (int i = k; i <= m; i++) {
        int tmp1 = f[m] / (f[i] * f[m - i]);
        int tmp2 = f[n - m] / (f[m - i] * f[n - 2 * m + i]);
        ans += tmp1 * tmp2;
    }

    cout << (double) ans * f[m] * f[n - m] / f[n] << '\n';
}

수식은 아래와 같다.

시그마 안에 있는 식을 정리하면 아래와 같다.

그런데 아래와 같이 구현하면 WA를 받게 된다.

for (int i = k; i < m + 1; i++) {
    ans += (double) (f[m] * f[n - m]) / (f[i] * f[m - i] * f[m - i] * f[n - 2 * m + i]);
}

답을 이렇게 계산하면 8 7 1 를 입력했을 때 1.022907992 가 출력되어, 확률이 1이 넘는 기이한 현상을 볼 수 있다.

이렇게 이상하게 계산되는 이유를 몰라서 한참을 헤맸는데, 생각해보니 C(n-m, m-i)에서 (n-m)이 (m-i)보다 작은 경우가 생길 수 있다. 8 7 1 이 이 경우 중 하나이다. 그래서 이 때 예외 처리를 해주어야 한다.

하지만 예외 처리를 따로 하지 않아도 해결할 수 있다.

for (int i = k; i <= m; i++) {
    int tmp1 = f[m] / (f[i] * f[m - i]);
    int tmp2 = f[n - m] / (f[m - i] * f[n - 2 * m + i]);
    ans += tmp1 * tmp2;
}

위와 같이 구현을 하면 된다. 하나의 조합 계산의 결과는 int이므로 각각을 계산하여 int로 저장한 후, 곱해서 ans에 더해주는 방식이다. 이렇게 하게 되면 (n-m)이 (m-i)보다 작은 경우에 자동으로 tmp2가 0이 되어 따로 예외 처리를 해줄 필요가 없는 것이다. (AC)