[백준 2225번] 합분해 - Kotlin

[백준 2225번] 합분해 - Kotlin

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

---

문제

• 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.
• 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우).
• 또한 한 개의 수를 여러 번 쓸 수도 있다.

---

입력

• 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

---

출력

• 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

---

풀이

private class Solution2225 {
    fun solution(n: Int, k: Int): Long {
        // w + x + y + z = 6
        // x + y + z = 6 - w
        // k - 1개로 6 - w 만드는 과정
        val dp = Array(k + 1) { LongArray(n + 1) { 1L } }

        for (row in 2 .. k) {
            for (col in 1 .. n) {
                dp[row][col] = (dp[row - 1][col] + dp[row][col - 1]) % 1_000_000_000
            }
        }

        return dp[k][n]
    }

}

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

    val (n, k) = br.readLine().split(" ").map(String::toInt)

    bw.append("${Solution2225().solution(n, k)}\n")
    bw.flush()

    br.close()
    bw.close()
}