백준 1359 복권 Kotlin (조합)

문제 출처 : https://www.acmicpc.net/problem/1359

1359번: 복권

문제

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

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

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

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

입력

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

출력

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

제한

• 2 ≤ N ≤ 8
• 1 ≤ M ≤ N-1
• 1 ≤ K ≤ M

알고리즘 분류

• 수학
• 브루트포스 알고리즘
• 조합론
• 확률론

풀이

이번엔 조합을 구하는 알고리즘이 아닌 조합 공식을 이용한 수학 문제이다.

확률이란 원하는 조건의 경우의 수 / 전체 경우의 수이다.

전체 경우의 수는 nCm으로 n개에서 m개를 뽑은 전체 경우의 수이다.

그럼 원하는 조건의 경우의 수는 어떻게 구할까?

조건을 보면 고른 m개의 수 중에 k개 이상! 겹치면 당첨이다.

k개 이상! 이기 때문에 결국 내가 뽑은 m개의 수에 당첨 번호가 k개, k+1개, ~~~, m개 있는 경우 모두를 더해줘야 하는 것이다.

따라서 mCk로 m개에서 k를 뽑았다면, 나머지 m-k자리에 들어갈 경우의 수는 (n-m)C(m-k)으로,

당첨된 모든 경우의 수는 result += combination(m,i)*combination(n-m,m-i)이 된다.

 

코드

val br = System.`in`.bufferedReader()

fun combination(a: Int, b: Int): Long{
    var n = a
    var r = b
    var nn =1L
    var rr =1L
    while(r>0){
        nn *=n--
        rr *=r--
    }
    return nn/rr
}


fun main() = with(System.out.bufferedWriter()){

    val (n,m,k) = br.readLine().split(' ').map{it.toInt()}

    var num1=0L
    val num2 = combination(n,m)
    for(i in k .. m){
        if(n-m < m-i) continue
        num1 += combination(m,i)*combination(n-m,m-i)
    }

    write("${num1/num2.toDouble()}\n")


    close()
}