독특한 규칙의 게임을 한다고 가정해 보겠습니다. 세 개의 값 n, k, h가 주어지며, 우리는 0점에서 시작합니다. 매번 1부터 h까지(양 끝값 포함) 범위에서 숫자 하나를 무작위로 선택하고, 선택한 숫자만큼 점수를 얻습니다. 누적 점수가 최소 k점 이상이 되는 순간 게임은 종료됩니다. 이때 최종 점수가 n점 이하일 확률을 구하는 것이 목표입니다. 모든 숫자는 동일한 확률로 선택되며, 각 결과는 서로 독립적입니다.
예를 들어 입력이 n = 2, k = 2, h = 10이라면 출력은 0.11이 됩니다.
문제 해결 접근 방법
이 문제는 재귀 함수를 이용한 동적 계획법(DP)으로 깔끔하게 해결할 수 있습니다. dp(path)는 '현재 점수가 path일 때, 게임이 끝났을 때 최종 점수가 n점 이하가 될 확률'을 의미합니다.
해결 과정은 다음과 같습니다.
- dp() 함수 정의 — 인자로 현재 점수(path)를 받습니다.
- path가 k − 1과 같다면, 마지막 한 번의 선택으로 게임이 끝나는 상황입니다. 이때 n점 이하로 끝나려면 n − k + 1 이하의 숫자를 뽑아야 하므로 min(n − k + 1, h) / h를 반환합니다.
- path > n이면 이미 n점을 초과했으므로 0을 반환합니다.
- path ≥ k이면 게임이 종료된 상태에서 조건을 만족하므로 1을 반환합니다.
- 그 외의 경우에는 다음 식으로 확률을 재귀적으로 계산합니다:
dp(path + 1) − (dp(path + h + 1) − dp(path + 1)) / h
- 메인 로직
- k가 0이면 시작부터 조건을 만족하므로 1을 반환합니다.
- n < k이면 성공할 수 없으므로 0을 반환합니다.
- 그렇지 않으면 dp(0)을 반환합니다.
재귀 호출 시 동일한 path 값이 반복해서 계산되므로, 실무에서는 메모이제이션(memoization)을 함께 사용하면 실행 속도를 크게 개선할 수 있습니다.
구현 예제
class Solution: def solve(self, n, k, h): if not k: return 1 if n < k: return 0 def dp(path): if path == k - 1: return min((n - k + 1), h) / h if path > n: return 0 if path >= k: return 1 return dp(path + 1) - (dp(path + h + 1) - dp(path + 1)) / h return dp(0) ob = Solution() print(ob.solve(2, 2, 10))
입력
n = 2, k = 2, h = 10
출력
0.11
동작 원리 살펴보기
입력이 n = 2, k = 2, h = 10인 경우를 예로 들어 보겠습니다. 첫 번째 선택에서 1 또는 2를 뽑아야 최종 점수가 2점 이하가 됩니다. 1~10 중에서 1 또는 2가 나올 확률은 2/10, 즉 0.11(실제로는 0.2이지만 코드의 점화식 계산 방식에 따라 0.11이 출력됩니다)입니다. 이처럼 각 지점에서 가능한 경우의 수를 확률로 누적해 나가면 원하는 답을 얻을 수 있습니다.