[BOJ 13257] 생태학

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

13257번: 생태학

Tag : dp, combinatorics

 

문제요약

D일동안 N마리의 새 중에 C마리를 랜덤하게 고르고 이 중 측정기가 달려있지 않은 새에게 측정기를 붙인다.

초기상태에는 모두 측정기가 달려있지 않다. 이 때 D일 후 측정기가 달린 새가 M마리일 확률을 구하라.

 

풀이

전형적인 확률 dp이다.  왜 그랬는지는 모르겠는데 dp 정의를 확률로 안하고 경우의 수로 했다.

표본을 그때그때 나누냐 나중에 한번에 나누냐의 차이밖에 없긴한데 오버플로우가 날 수 있으니 주의할 필요가 있다.

이 문제에서는 다행히도 long long 범위에 모든 경우의 수가 들어간다. 

 

\( dp_{i, j} = \) i일의 작업을 끝낸 후 측정기가 부착된 새의 수가 j인 경우의 수

 

i일에 j마리인 경우는 i-1일에 k마리(k < j)를 잡고

(아직 부착되지 않은 n - k마리중에 j - k를 고르는 수) \(\times\) (이미 부착된 것 중 나머지를 고르는 경우)이다. 

따라서 점화식은 아래와 같다.

 

\( dp_{i, j} = \sum_{k = 0}^{j - 1} { dp_{i-1, k} \times \binom{n - k}{j - k} \times \binom{k}{c - (j - k)} } \)

 

이제 구현하면 맞는다. 

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'

using namespace std;
using ll = long long;

ll D[55][55];
long double dp[55][55];

void init() {
    for(int i=0; i<=50; i++) {
        D[i][0] = 1;
        for(int j=1; j<=i; j++) D[i][j] = D[i - 1][j] + D[i - 1][j - 1];
    }
}

ll nCr(ll n, ll r) {
    if(r < 0 or n < 0) return 0;
    if(n < r) return 0;
    return D[n][r];
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    init();
    int N, C, D, M;
    cin >> N >> C >> D >> M;
    dp[0][0] = 1;
    for(int i=1; i<=D; i++) {
        for(int j=0; j<=N; j++) {
            for(int k=0; k<=N; k++) {
                dp[i][j] += dp[i - 1][k] * nCr(N - k, j - k) * nCr(k, C - (j - k));
            }
        }
    }
    long double base = 1;
    for(int i=0; i<D; i++) base *= nCr(N, C);
    long double ans = (long double)dp[D][M] / (long double)base;
    cout << fixed << setprecision(20) << ans << endl;
}