[백준] 1359_복권 / 수학, 조합

Algorithm/Baekjoon Oline Judge - Java

[백준] 1359_복권 / 수학, 조합

StrongMin 2025. 1. 16. 22:20

Sliver

문제

어제, 지민이는 몰래 리조트에 갔다가 입구에 걸려있는 복권 광고를 하나 보았다.

“1부터 N까지의 수 중에 서로 다른 M개의 수를 골라보세요. 저희도 1부터 N까지의 수 중에 서로 다른 M개의 수를 고를건데, 적어도 K개의 수가 같으면 당첨입니다.!”

지민이는 돌아오면서 자신이 복권에 당첨될 확률이 궁금해졌다.

지민이가 복권에 당첨될 확률을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 N, M, K가 주어진다.

출력

첫째 줄에 지민이가 복권에 당첨될 확률을 출력한다. 절대/상대 오차는 10-9까지 허용한다.

풀이

import java.util.*;
import java.io.*;

class Main {
    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());
        int K = Integer.parseInt(st.nextToken());

        // N개에서 M개를 뽑는 경우의 수
        // nCm = N! / M!(N-M)!
        double total = combination(N, M);

        // 적어도 K개를 맞추는 경우의 합
        // 맞춘숫자 i개가 포함되면서 틀릿숫자m-i개가 포함되는 조함
        double min = 0;
        for(int i=K; i<=M; i++){
            if(i>N) break;
            min += combination(M, i) * combination(N-M, M-i);
        }
        
        
        System.out.println(min/total);
    }

    // nCr
    public static double combination(int n, int r){
        if(r>n) return 0;
        double result = 1;
        for(int i=0; i<r; i++){
            result *= (n-i);
            result /= (1+i);
        }
        return result;
    }
}

해결방법

전체 경우의 수를 계산한다.
-> N개 중 개를 뽑는 경우의 수를 계산한다. (Total 경우의 수)
적어도 K개를 맞추는 경우의 수를 계산한다.
-> M개를 뽑았을 때, 적어도 K개를 맞추는 경우의 수를 계산한다. (Min 경우의 수)
-> M개에서 i(K이상 M이하) 개를 맞추었을 때의 경우의 수 * 나머지(N-M)에서 맞지 않는 수(M-i)를 뽑았을 때의 의 경우의 수
적어도 K개를 맞추는 경우의 수를 전체 경우의 수로 나누어 확률을 계산한다.