[백준] 11051번: 이항 계수 2 - Kotlin[코틀린]

문제

 

11051번: 이항 계수 2

 

---

풀이

 

 파스칼 삼각형을 이용해 점화식을 만들고 이항 계수를 계산해주면 된다. 아래의 이미지는 파스칼 삼각형을 쉽게 이해할 수 있도록 설명해 준다.

이미지 출처 - 위키 백과

 파스칼 삼각형은 각 단계의 처음과 끝은 1로 채워주고 그 사이의 항들은 윗 단계에서 더해주는 것으로 계산한다. 이에 대한 수학적 증명은 아래와 같다.

 

$$\displaystyle \binom{n-1}{r-1}+\binom{n-1}{r}=\frac{\left(n-1\right)!}{\left(r-1\right)!\left(n-r\right)!}+\frac{\left(n-1\right)!}{r!\left(n-r-1\right)!}=\frac{\left(n-1\right)!r}{r!\left(n-r\right)!}+\frac{\left(n-1\right)!\left(n-r\right)}{r!\left(n-r\right)!}=\frac{n!}{r!\left(n-r\right)!}=\binom{n}{r}$$

 

 위의 성질을 점화식으로 나타낼 수 있다.

  - dp[i][0] = 1, dp[i][i] = 1

  - dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

 dp 배열을 선언하고 반복문을 통해 점화식 계산을 해주고 10007으로 나눈 값을 출력해주면 된다.

 

---

코드

 

import java.util.*

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val st = StringTokenizer(br.readLine())
    val num = st.nextToken().toInt()
    val k = st.nextToken().toInt()

    val dp = Array(num + 1){ IntArray(num + 1) }

    for(i in 1 .. num) {
        dp[i][i] = 1
        dp[i][0] = 1
    }
    for(i in 2..num) {
        for (j in 1..i) {
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % 10007
        }
    }

    bw.write("${dp[num][k]}")
    bw.flush()
    bw.close()
    br.close()
}