백준 2225 합분해 Kotlin (dp)

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

2225번: 합분해

문제

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

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

입력

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

출력

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

알고리즘 분류

• 수학
• 다이나믹 프로그래밍

풀이

dp 문제이다.

항상 dp는 코드만 간단하지 푸는 과정은 간단하지 않았다.

본인은 우선 간단한 케이스를 직접 구해보고, 이를 통해 규칙을 찾는 것을 먼저 한다.

얻어걸린 규칙이 맞긴 했지만, 왜 이렇게 되는지 이해를 하지 못해 풀이를 찾아본 결과 풀이는 다음과 같다고 한다.

 

dp[k][n] : k개를 더해 n을 만드는 경우의 수

2차원 dp를 우선 정의한다.

 

n이 6이라 하고, k가 4라고 하자.

a + b + c + d = 6인 모든 경우를 찾아야 하는데,

a + b + c = 6-d 인 모든 경우와 같다.

즉 k개로 n을 만드는 경우의 수와 k-1개로 n-d을 만드는 경우의 수가 같다.

dp[k][6] = dp[k-1][n-d]

d는 0부터 6까지의 값이 올 수 있으므로 

dp[k][6] = dp[k-1][0] + dp[k-1][1] + dp[k-1][2] + dp[k-1][3] + dp[k-1][4] + dp[k-1][5] + dp[k-1][6]이 된다. 

 

이 점화식을 가지고 3중 포문으로 풀어도 되지만, 말했다시피 본인은 그래프를 통해 규칙을 찾아냈고,

위의 점화식으로도 그래프를 그려본 결과 내가 생각한 규칙이 맞았다.

 

k＼n	0	1	2	3
1	1	1	1	1
2	1	2	3	4
3	1	3	6	10

n이 0이거나 k가 1인 경우 k로 n을 만드는 경우는 무조건 1일 수밖에 없고, 나머지 부분은

dp[k][n] = dp[k-1][n] + dp[k][n-1]이란 걸 알 수 있다.

이 점화식을 이용하면 2중 포문으로 풀 수 있다.

하지만 이를 증명하진 못하겠다.

이를 증명한 글을 발견하거나 본인이 안다면 저도 알려주세요.. 제가 지금 정신이 없습니다

 

코드

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

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

    val (n,k) = br.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
        }
    }
    write("${dp[k][n]}")

    close()
}