[BOJ] 1413 박스 안의 열쇠 - P5

문제풀이

1. dp[박스의 개수][열쇠의 개수] = 경우의 수로 두고 dp테이블을 채워나간다.

---

주의사항

---

소요시간

30분

---

package 백준.Platinum.P5.p1413_박스안의열쇠

const val EMPTY = -1L
fun main() {
    fun gcd(a: Long, b: Long): Long = if (minOf(a, b) == 0L) maxOf(a, b)
    else gcd(minOf(a, b), maxOf(a, b) % minOf(a, b))
    val (N, M) = readln().trim().split(" ").map(String::toInt)
    val dp = Array(N + 1) { n -> LongArray(N + 1) { m -> if (n == 0) 1 else if (m == 0) 0 else EMPTY } }
    fun dp(n: Int, m: Int): Long {
        if (dp[n][m] == EMPTY) dp[n][m] = dp(n - 1, m - 1) + (n - 1) * dp(n - 1, m)
        return dp[n][m]
    }
    val B = dp(N, N)
    val A = dp(N, M)
    val gcd = gcd(A, B)
    println("${A / gcd}/${B / gcd}")
}

https://github.com/TaeGN/Algorithm/blob/master/src/%EB%B0%B1%EC%A4%80/Platinum/P5/p1413_%EB%B0%95%EC%8A%A4%EC%95%88%EC%9D%98%EC%97%B4%EC%87%A0/p1413_%EB%B0%95%EC%8A%A4%EC%95%88%EC%9D%98%EC%97%B4%EC%87%A0.kt

---

문제링크

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