[Swift 알고리즘] 백준 2225 합분해

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를 사용해서 풀어야 한다. 우리가 생각할 것 1. 숫자를 몇개 사용하여 만들 지

상상해봅시다

1개

0을 만드는데 한개의 숫자가 필요하다면? -> "0"

1을 만드는데 한개의 숫자가 필요하다면? -> "1"

....

6을 만드는데 한개의 숫자가 필요하다면? -> "6"

 

 

2개

0을 만드는데 두개의 숫자가 필요하다면? -> "0 + 0"

1을 만드는데 두개의 숫자가 필요하다면? -> "0 + 1", "1 +0"

2을 만드는데 두개의 숫자가 필요하다면? -> "0+2", "1+1", "2+0"

 

key point = 2을 만드는데 두개의 숫자가 필요한데 이는 이전의 구한 값을 통해 생각해 볼 수 있습니다.

i는 2 j는 2 (편의상 ind을 0부터 시작을 안했습니다.)

일단 dp[i][j-1]을 생각해 보면 "0 + 1", "1 + 0 "입니다. 우리는 왼쪽에 1을 더한다고 가정해 봅시다. "0 + 2", "1 + 1"이 됩니다.

dp[i-1][j]을 생각해 보면 "2"밖에 없습니다. 우리는 왼쪽에 0을 더하낟고 가정해 봅시다. "2 + 0"

이를 합치게 되면 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]이란 점화식을 얻을 수 있습니다.

 

하나 더 i가 3이고 J가 1일 때 한번 더 해봅시다

dp[i][j-1] = "0 + 0 + 0"

dp[i - 1][j] = "0 + 1", "1 + 0"

이것을 합치면 dp[i][j] = dp[i][j - 1] + dp[i - 1][j] = "0 + 0 + 1", "0 +1 + 0, 1 + 0 + 0" 이 나오게 됩니다.

 

 

이를 코드로 작성하게 된다면

 

 

func sol() {
    let inputVal = readLine()!.split(separator: " ").map{Int($0)!}
    let nVal = inputVal[0]
    let kVal = inputVal[1]
    let constVal = 1000000000
    var dp = Array(repeating: Array(repeating: 1, count : nVal + 1 ), count: kVal)
    for i in 1..<kVal {
        for j in 1...nVal {
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % constVal
        }
    }
    print(dp.last!.last!)
}

sol()