복권 (BOJ 1359)

문제

이미지클릭

문제 설명

1~n의 숫자 중에서 무작위로 m개를 뽑았을 때 k개가 같다면 복권에 당첨된다.

문제 해설

• 기본적으로 조합을 활용해 준다.
• f(n, r)은 조합 공식에서 C(n, r)을 계산한다.

double f(int n, int r){
    int x=1, y=1;
    while(r){
        y *= n, x *= r;
        n--, r--;
    }
    return y/x;
}

 

• 다음으로 전체 경우의 수를 구해준다.

double x = f(n, m);

• 반복문 k부터 m까지 반복하면서 특정 조건을 만족하는 조합을 구해준다.

while(m >= k){
    if(n-m >= m-k) ans += f(m, k) * f(n-m, m-k) / x;
    k++;
}

• if (n-m >= m-k) 조건은 가능한 조합인지 체크하는 역할을 한다. 즉, f(m, k) * f(n-m, m-k)가 유효한지 확인해 준다.

최종 코드

#include <ibits/stc++.h>
using namespace std;
int n,m,k;
double ans;
double f(int n,int r){
    int x=1, y=1;
    while(r){
        y*=n,x*=r;
        n--,r--;
    }
    return y/x;
}
int main(){
    cin >> n >> m >> k;
    double x = f(n,m);
    while(m>=k){
        if(n-m >= m-k)ans += f(m,k) * f(n-m,m-k)/x;
        k++;
    }
    cout<<fixed<<setprecision(20)<<ans;
}

이미지클릭