문제 설명
Rima가 카드 게임 "21"에서 아이디어를 얻은 다음과 같은 게임을 한다고 가정해 보겠습니다. Rima는 0점에서 시작하며, 자신의 점수가 K 미만일 때까지 계속해서 숫자를 뽑습니다. 매번 숫자를 뽑을 때마다 주어진 정수 W에 대해 [1, W] 범위 안의 정수 포인트를 무작위로 얻게 됩니다. 각 추첨은 서로 독립적이며, 모든 결과는 동일한 확률로 나타납니다. Rima는 점수가 K점 이상이 되면 숫자 뽑기를 중단합니다.
이때 우리가 구해야 하는 것은 Rima가 최종적으로 N점 이하를 가질 확률입니다.
예를 들어 N = 6, K = 1, W = 10이라면 답은 0.6입니다. Rima는 단 한 장의 카드만 뽑고 멈추기 때문에, 10번의 경우 중 6번은 N = 6점 이하가 되기 때문입니다.
풀이 접근 방법
이 문제는 동적 계획법(Dynamic Programming)과 슬라이딩 윈도우(Sliding Window) 기법을 활용하면 효율적으로 해결할 수 있습니다. dp[i]를 "i점에 도달할 확률"로 정의하고, 직전 W개의 상태 확률 합을 관리하면 매번 전체 합을 다시 계산하지 않아도 되므로 시간 복잡도를 O(N)으로 줄일 수 있습니다.
알고리즘 단계
- K가 0이거나 N >= K + W인 경우, Rima가 반드시 N 이하가 되므로 1을 반환합니다.
- 크기가 N + 1인 배열 dp를 만들고, dp[0] := 1로 초기화합니다. (0점에서 시작)
- wsum := 1.0, ret := 0.0으로 설정합니다. (wsum은 최근 W개 확률의 합, ret는 최종 정답)
- i를 1부터 N까지 반복합니다:
- dp[i] := wsum / W (직전 W개 상태의 평균 확률)
- i < K이면 wsum에 dp[i]를 더하고, 그렇지 않으면(즉 i >= K) ret에 dp[i]를 누적합니다.
- i – W >= 0이라면 윈도우에서 벗어난 dp[i - W]를 wsum에서 뺍니다.
- 최종적으로 ret을 반환합니다.
다음 구현 예제를 통해 더 잘 이해해 보겠습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
double new21Game(int N, int K, int W) {
if(K == 0 || N >= K + W) return 1.0;
vector <double> dp (N + 1);
dp[0] = 1;
double Wsum = 1.0;
double ret = 0.0;
for(int i = 1; i <= N; i++){
dp[i] = Wsum / W;
if(i < K){
Wsum += dp[i];
}else ret += dp[i];
if(i - W >= 0) Wsum -= dp[i - W];
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.new21Game(6, 1, 10));
}입력
6 1 10
출력
0.6
마무리
이 풀이의 핵심은 각 점수에 도달할 확률을 이전 W개 상태의 확률 합으로 정의하는 것입니다. 단순하게 매번 합을 새로 구하면 O(N×W)의 시간이 걸리지만, 슬라이딩 윈도우로 합을 유지·갱신함으로써 O(N)의 시간 복잡도와 O(N)의 공간 복잡도로 최적화할 수 있습니다.