[Kotlin] 백준 2225번 : 합분해 <Gold 5>

https://www.acmicpc.net/problem/2225

2225번: 합분해

 

Code

---

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

const val MOD = 1000000000

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))){
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val (n, k) = readLine().split(" ").map { it.toInt() }
    val dp = Array(n + 1) { IntArray(k + 1) { 1 } }

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

    bw.write("${dp[n][k]}")

    bw.flush()
    bw.close()
}

 

 

---

DP문제의 핵심은 점화식이다.

DP문제의 특성상 이전값이 다음 값에 영향을 주기때문에 어지간하면 규칙이 존재하고, 점화식을 구할 수 있다. 

 

이 문제의 경우에는 솔직히 수학적으로 왜 저런 점화식이 나오는지 모르겠다.

그냥 하나씩 하나씩 작성하면서 규칙을 찾아봤더니 저런 규칙이 나와서 사용했다.

 

이처럼 수학적인 점화식을 못구하겠다면, 표를 그려보는 것도 하나의 방법이다.