[BOJ-17213][백준 17213] 과일 서리 [SILVER-2][Solved by Kotlin]

입력 및 출력

• 입력: 첫째 줄에 과일의 종류 수 N(1 ≤ N ≤ 10)이 주어진다.
  둘째 줄에 훔치려 하는 과일의 개수 M(N ≤ M ≤ 30)이 주어진다.
• 출력: 첫째 줄에 훔칠 수 있는 경우의 수를 출력한다.

풀이

민건이는 N 종류의 과일을 재배 중이라고 하고있다.
이때, 지환이가 과일을 훔치게 되는데, 민건이가 가지고 있는 모든 과일을 하나씩 훔치면서, 훔칠 수 있는 경우의 수를 찾는 것이다. 

입력 예시를 보자.
과일의 종류의 수가 3개이고, 훔치려는 과일의 개수가 10개이다.
모든 종류의 과일을 적어도 1개씩을 훔쳐야 하므로, 뽑은 과일의 종류를 또 훔치는 것이 허용된다.
이렇게 하여 총 10개를 뽑는 것이다.

결론지으면 3가지 종류 중 중복을 허락하여 10개를 뽑으라는 의미이다. 이것은 중복조합으로 해결할 수 있다.

코드

import java.io.BufferedWriter
import java.io.OutputStreamWriter
import java.util.*


val bw = BufferedWriter(OutputStreamWriter(System.out))
fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val m = readLine().toInt()
    val answer: Long = factorial(m-n+1, m-1) / factorial(1, n-1)
    bw.write("$answer")

    bw.flush()
    bw.close()
    close()
}
fun factorial(a: Int, b: Int): Long {
    var res = 1L
    for(i in a..b) {
        res *= i
    }
    return res
}

중복조합의 공식은 다음과 같고 조합 공식으로 치환이 가능하다.

$$ {}_n \mathrm{ H }_k = {}_n{}_+{}_k{}_-{}_1 \mathrm{ C }_n{}_-{}_1 $$

조합은 다음 팩토리얼을 사용한 다음 공식으로 치환할 수 있다.

$$ {}_n \mathrm{ C }_k = \frac{n!}{k!(n-k)!} $$

이 공식을 적용해서 factorial 함수를 만들어 중복조합을 계산한다.
여기서 n의 범위가 0부터 10이고, k의 범위가 n부터 30이라는 점을 감안하여 factorial 함수의 return type은 Long 타입으로 선언해준다.

결과

괜찮은 결과를 얻을 수 있었다.