[LeetCode] 837. New 21 Game

문제 요약

• 0점에서 시작해, 점수가 k 미만이면 1 ~ maxPts 중 하나를 같은 확률로 뽑아 더한다.
• 점수가 k 이상이 되면 멈춘다.
• 멈췄을 때 점수가 n 이하일 확률을 구한다.

변수의 역할을 나누면 헷갈리지 않는다.

변수	역할
k	멈추는 기준
maxPts	카드 한 장의 최댓값
n	버스트 기준선 (게임 진행에는 관여하지 않고 결과 판정에만 쓰임)

n=21, k=17, maxPts=10 이면 블랙잭 딜러 규칙과 같다.

핵심 아이디어

dp[i] = 게임 도중 점수가 정확히 i 가 될 확률

점수 i 에 오려면 직전 점수 j 에서 카드 i - j 를 뽑아야 한다.

• j 는 i - maxPts ~ i - 1 범위 (카드가 1 ~ maxPts 이므로)
• j < k 여야 한다 (k 이상이면 이미 멈춰서 더 뽑지 않음)
• 특정 카드가 나올 확률은 1 / maxPts

dp[i] = (조건을 만족하는 dp[j] 의 합) / maxPts

멈추는 칸은 k ~ n 이므로 답 = dp[k] + ... + dp[n] 이다.

매번 합을 새로 구하면 O(n · maxPts) 라서, 합을 슬라이딩 윈도우(windowSum) 로 유지한다.

빠른 반환

if (k === 0 || n >= k - 1 + maxPts) return 1;

• k === 0: 한 장도 뽑지 않고 0점에서 끝난다. 반복문은 "0점에서 반드시 한 장 뽑는다"를 전제로 하므로 따로 걸러야 한다.
• n >= k - 1 + maxPts: 최대로 나올 수 있는 점수는 k - 1(뽑기 직전 최대)에 maxPts(가장 큰 카드)를 더한 값이다. 최악의 경우에도 n 이하라면 버스트할 수 없다.

코드

function new21Game(n: number, k: number, maxPts: number): number {
    if (k === 0 || n >= k - 1 + maxPts) return 1;

    const dp = Array(n + 1).fill(0);
    dp[0] = 1;
    let windowSum = 1;
    let probability = 0;

    for (let i = 1; i <= n; i++) {
        dp[i] = windowSum / maxPts;
        if (i < k) windowSum += dp[i];
        else probability += dp[i];
        if (i - maxPts >= 0 && i - maxPts < k) windowSum -= dp[i - maxPts];
    }

    return probability;
};

• i < k: 아직 더 뽑으므로 다음 칸의 출발점으로 윈도우에 넣는다.
• i >= k: 여기서 멈추므로 윈도우에 넣지 않고 결과에 더한다.
• 빼기: 카드 최댓값보다 멀어진 칸을 윈도우에서 뺀다. 윈도우에는 k 미만인 칸만 들어가므로 < k 인 칸만 뺀다.

헷갈렸던 점

1. 반복문을 k 까지만 돌리면 안 된다. 멈추는 것은 앨리스이고, 반복문은 점수 칸을 채운다. 멈추는 점수는 k 하나가 아니라 k ~ n 전부다.
2. k 미만인 칸은 결과에 더하지 않는다. 그 칸을 지나서 계속 뽑기 때문에 최종 점수가 아니다.
3. k = 0 예외. n=1, k=0, maxPts=3 에서 빠른 반환이 없으면 0점에서 카드를 뽑는 것처럼 계산돼 1/3 이 나온다. 정답은 1이다.

복잡도

• 시간 O(n), 공간 O(n)