[Swift] 백준 2225 - 합분해

문제 링크

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구해야한다.

• K가 1인 경우 : 숫자에 관계없이 경우의 수는 항상 1이다.
• K가 2인 경우 : 경우의 수는 항상 N+1이다.
  • 예를 들어, 숫자가 6인 경우 (0,6), (1,5), (2,4), (3,3), (4,2), (5,1), (6,0) 으로 0에서 6까지의 개수 7이다.
• K > 2 인경우 : 경우의 수는 0부터 N까지의 K-1일 때의 경우의 수의 합이다.
  • 사진 참고
• N이 1인 경우 : 경우의 수는 항상 K개이다
  • N= 1이고 K = 3인경우 -> (0,0,1), (0,1,0), (1,0,0)

따라서 K개의 합으로 표현되는 정수 N의 값들을 포함하는 2차원 배열인 dp를 사용하여야 한다.
예를들어, 3개의 합으로 표현되는 정수 5의 값을 dp[3][5]에 넣는것이다.

최종 코드

import Foundation

let nums = readLine()!.split(separator: " ").map { Int(String($0))!}

let N = nums[0]
let K = nums[1]

var dp = Array(repeating: Array(repeating: 1, count: 201), count: 201)

for i in 1..<201 {
    dp[2][i] = i + 1
}

for i in 1..<201 {
    dp[i][1] = i
}

if K > 2 && N > 1 {
    for i in 3...K {
        for j in 2...N {
            var sum = 0
            for k in 0...j {
                sum = (sum + dp[i-1][k])%1000000000
            }
            dp[i][j] = sum%1000000000
        }
    }
}
print(dp[K][N]%1000000000)

• 배열을 만들 때 값이 1인 배열을 만들었기 때문에 K가 1인 경우를 따로 다루지 않아도 된다.