Daily LeetCode Challenge - 837. New 21 Game

Problem From.

https://leetcode.com/problems/new-21-game/

오늘 문제는 1부터 maxPts 까지 나올수 있는 카드 뭉치에서 카드를 뽑을때, k 보다 적은 포인트를 뽑는다고 가정했을때, 마지막까지 뽑은 카드들의 합이 n 과 같거나 작을 확률을 반환하는 문제였다.

이 문제는 DP 로 풀 수 있었는데,
먼저 dp[0] 에는 어떤 카드를 뽑던 1보다는 커지므로 1.0 을 넣어두고 다음 부터 계산을 한다.
i 번째에 도달했을때의 확률은 그 전까지의 확률을 maxPts 로 나눈게 되며, 만약 그 수가 k 보다 작다면 확률을 계속해서 더해나가고, 그 수가 k 보다 크다면 멈추게된다.

class Solution {
    fun new21Game(N: Int, K: Int, maxPts: Int): Double {
        if (K == 0) return 1.0
        val probability = DoubleArray(K)
        for (i in (K - 1 downTo 0)) {
            if (i == K - 1) {
                probability[i] = 1.0 / maxPts * (Math.min(N, K - 1 + maxPts) - K + 1)
            } else {
                probability[i] = (1.0 + 1.0 / maxPts) * probability[i + 1] - 1.0 / maxPts * when {
                    i + 1 + maxPts > N -> 0.0
                    i + 1 + maxPts >= K -> 1.0
                    else -> probability[i + 1 + maxPts]
                }
            }
        }
        return probability[0]
    }
}