BOJ-2225 합분해 Swift

문제

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

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

입력

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

출력

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

내가 푼 풀이

- N이 주어졌을때, 0부터 N까지 k번을 더해서 N을 만드는 경우의 수를 구한다.

- K = 1 인경우, 한번만 더해서 N을 만드려면 N 자기 자신을 더하는 방법 1가지다.

- K = 2 인경우, 두번 더해서 N을 만드려면 , 0 + N , 1 + (N-1), ... , N + 0 으로 N가지이다.

- 이를 "dp[n][k] = 0부터N까지의 정수 K번 더해서 합이 N이되는 경우의수" 로 정의하자.

- K = 1 인경우 자기 자신만 더하면 되므로 dp[n][1] = 1

- K = 2 인경우 자기 자신을 1씩차감한만큼 더해주면 되므로, dp[n][2] = n 이된다.

- 이제 K = 3 부터는 이전의 값을 저장된 값을 사용하려한다.

- 3번 더해서 N을 만드는 경우의 수를 초기값이 0부터 N까지의 경우의수를 생각해보자.

예시로 N = 3 , K = 3 일때

• 초기값 = 0 이라면, 나머지 3, 두번을 더해서 3을 만들때 => dp[3][2]
• 초기값 = 1 이라면, 나머지 2, 두번을 더해서 3을만들때 => dp[2][2]
• 초기값 = 2 이라면, 나머지 1, 두번을 더해서 3을 만들때 => dp[1][2]
• 초기값 = 3 이라면 나머지 0, 두번을 더해서 3을 만들때 => dp[0][2]

로 나타낼 수 있다.

이는 dp[n][k] = k번 더해서 합이 n이되는 경우의 수 이기때문이다.

위를 바탕으로 N = 5, K = 3 일때의 dp를 구하면 다음과 같다.

DP	1	2	3
0	1	1	1
1	1	2	3
2	1	3	6
3	1	4	10
4	1	5	15
5	1	6	21

따라서 0부터5까지 정수를 3번 더해서 합이 5가되는 경우의 수는 21이 된다.dp[5][3]

 

이를 코드로 구현하면 다음과 같다.

 

import Foundation

var input = readLine()!.split(separator: " ").map{ Int($0)! }
var dp = Array(repeating: Array(repeating: 0, count: input[1]+1), count: input[0]+1)

// DP 입력
// dp[n][k] = dp[n][k] + dp[i][k-1] (i는 0부터 n까지의 정수)
for i in 1...input[1] {
    for j in 0...input[0] {
        if i == 1 || j == 0 {
            dp[j][i] = 1
            continue
        }
        for k in 0...j {
            dp[j][i] = (dp[j][i] + dp[k][i-1]) % 1000000000
        }
    }
}
print(dp[input[0]][input[1]])