2225번: 합분해 - Kotlin

2225번: 합분해

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

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

출력

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

 

 

나의 풀이

이 문제는 DP를 사용해야 하는 문제이다. 이 문제의 특징은 한 개의 수를 여러 번 쓸 수 있고, 0을 포함할 수 있다는 것이다.

 이 말은 만약 입력이 [1, 4] 가 들어간다고 했을 때, (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1) 이렇게 4가지가 나올 수 있다는 것이다. 

 

이걸 안 이후로는 접근방식을 어떻게 가져가야 하는지 알게 되었다. 일단 이 문제는 만약 1부터 k까지 가능한 경우의 수를 구해야 한다. 

 

dp[k][4] = dp[k-1][0] + dp[k-1][1] + dp[k-1][2] + dp[k-1][3] + dp[k-1][4]

 

만약 n이 4일때에 답을 구하려고 한다면 위의 점화식을 만족하게 된다.

 

dp[k][3] = dp[k-1][0] + dp[k-1][1] + dp[k-1][2] + dp[k-1][3]

 

그리고 n이 3일 때의 점화식이 위와 같음으로 n이 4일 때의 점화식을 다음과 같이 바꿀 수 있다.

 

dp[k][4] = dp[k][3] + dp[k-1][4]

 

이로 최종 점화식을 다음과 같이 구할 수 있다.

 

dp[k][n] = dp[k-1][n] + dp[k][n-1]

 

fun main() = with(System.`in`.bufferedReader()) {
    val (n, k) = readLine().split(" ").map{ it.toInt() }
    val dp = Array(k + 1) { LongArray(n + 1) { 1 } }

    for(i in 2 ..k){
        for(j in 1 ..n){
            dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000000
        }
    }

    println(dp[k][n])
}