2023.05.25 Today's Challenge

fabichoi 2023. 5. 25. 23:45

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

New 21 Game - LeetCode

Can you solve this real interview question? New 21 Game - Alice plays the following game, loosely based on the card game "21". Alice starts with 0 points and draws numbers while she has less than k points. During each draw, she gains an integer number of p

leetcode.com

블랙잭과 비슷. DP로 푸는 문제

class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        dp = [0] * (n+1)
        dp[0] = 1
        s = 0
        if k > 0:
            s = 1
        for i in range(1, n+1):
            dp[i] = s/maxPts
            if i < k:
                s += dp[i]
            if i - maxPts >= 0 and i - maxPts < k:
                s -= dp[i-maxPts]
        return sum(dp[k:])