백준 1359번: 복권

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

 

1부터 N까지의 수 중에서 서로 다른 M개를 두명이서 뽑을 때 K개 이상 겹칠 확률를 구하는 문제이다. M개를 뽑는 경우의 수로 K개 이상 같은 수를 뽑는 경우의 수를 나누어 주면 된다.

 

전체 경우의 수는 N개에서 M개를 뽑는 조합이며(nCm), K개 이상 뽑는 경우의 수는 M개의 숫자 중 K부터 M개까지 뽑고(mCk), 나머지는 N개의 수 중 M이 아닌 수를 뽑는((n-m)C(m-k)) 모든 경우의 수를 구하는 것이다.

double totalCount = combination(n, m);
double kCount = 0;
for (int i = k; i <= m; i++) {
    if (n - m >= m - i) {
        kCount += combination(m, i) * combination(n - m, m - i);
    }
}

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 복권1359 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken()), k = Integer.parseInt(st.nextToken());
        br.close();
        double totalCount = combination(n, m);
        double kCount = 0;
        for (int i = k; i <= m; i++) {
            if (n - m >= m - i) {
                kCount += combination(m, i) * combination(n - m, m - i);
            }
        }
        System.out.print(kCount / totalCount);
    }
    
    private static long combination(int n, int m) {
        long result = 1L;
        for (int i = 0; i < m; i++) {
            result *= (n - i);
            result /= (i + 1);
        }
        return result;
    }
}