문제Permalink

Link

코드Permalink

class Solution {

  public double new21Game(int n, int k, int maxPts) {
    if (k == 0 || n >= k + maxPts) {
      return 1;
    }
    double[] dp = new double[n + 1];
    dp[0] = 1;
    double sum = 1;
    double result = 0;
    for (int idx = 1; idx <= n; idx++) {
      dp[idx] = sum / maxPts;
      if (idx < k) {
        sum += dp[idx];
      } else {
        result += dp[idx];
      }
      if (idx >= maxPts) {
        sum -= dp[idx - maxPts];
      }
    }
    return result;
  }

}

결과Permalink

Link

설명Permalink

1. 블랙잭(21 게임)을 기반으로 0점부터 시작하여 [1, maxPts] 범위의 균일한 확률의 정수를 추첨할 때, k점 이상 받아 멈출 경우 점수가 n 이하일 확률을 구하는 문제이다.

2. k가 0으로 시작과 동시에 끝나거나, n이 $k + maxPts$보다 크거나 같아 어떠한 값을 뽑아도 n 이하인 값이면 점수가 무조건 n 이하이므로 1을 주어진 문제의 결과로 반환한다.

3. 문제 풀이에 필요한 변수를 정의한다.
   • dp는 각 위치인 점수에 따른 확률을 구하기 위한 배열로, $n + 1$ 크기로 초기화하여 첫 값을 1로 넣어준다.
   • sum은 dp의 마지막 값을 구하기 위한 누계 확률 값으로, 1로 초기화한다.
   • result는 점수가 n 이하일 확률을 저장할 변수로, 0으로 초기화한다.
4. 1부터 n 이하까지 idx를 증가시키며 아래를 수행한다.
   • dp의 idx번째 위치에 $\frac{sum}{maxPts}$를 넣어준다.
   • idx가 k보다 낮으면 sum에, 아니면 result에 dp의 idx번쨰 값을 더해준다.
   • idx가 maxPts 이상인 추첨의 점수를 벗어나는 경우, sum에 dp의 $idx - maxPts$번째 값을 빼서 확률을 계산한다.
5. 반복이 완료되면 계산된 확률인 result를 주어진 문제의 결과로 반환한다.

소스Permalink

Sample Code는 여기에서 확인 가능합니다.