[백준] 13251번: 조약돌 꺼내기

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

문제

알고리즘 접근 방법

1번색에서 K개 뽑기 + 2번색에서 K개 뽑기 + .. + M번색에서 K개 뽑기
를
N개에서 K개 뽑기 로 나누면 된다.

M = 3 이고
[5 6 7]
K = 2 라고 예를 들면

(5C2 + 6C2 + 7C2) / (5+6+7)C2

NCK = N! / K!(N-K)! 인데 그러면 여기서 K!는 다 같으므로 없앨 수 있다.

고로 54 + 65 + 75 / 1817 이런식으로 계산하면 된다.

풀이

#include <iostream>

using namespace std;

int M, K;
int s[50];

int main(){

    scanf("%d", &M);
    int sum = 0; // 조약돌 전체 개수 N
    for(int i=0; i<M; i++){
        scanf("%d", &s[i]);
        sum += s[i];
    }

    scanf("%d", &K);

    double a=0, b=0, tmp=0;

    for(int i=0; i<M; i++){
        tmp = 1.0;
        for(int j=0; j<K; j++)  
            tmp *= s[i] - j;
        a += tmp;
    }

    b = 1.0;
    for(int j=0; j<K; j++)
        b *= sum-j;

    printf("%.15lf", (a/b));

    return 0;
}

정리

dp로 직접 다 조합 계산해보려다가 실패했다 .. 더 쉬운 방법이 있었뇌