LeetCode 808. Soup Servings (확률 DP 문제 풀이)

1. 문제 소개

두 종류의 수프 A와 B가 있고, 처음에는 각각 n mL씩 들어 있습니다.
게임은 다음 규칙으로 진행됩니다.

---

매 턴, 4가지 동작 중 하나를 확률 0.25로 선택:

선택A 감소량B 감소량

1	100	0
2	75	25
3	50	50
4	25	75

규칙

• A 또는 B 중 하나라도 0 이하가 되면 게임 즉시 종료
• 줄이려는 양이 남은 양보다 많으면, 남은 만큼만 줄임
• A가 먼저 소진될 확률 + A와 B가 동시에 소진될 확률의 절반을 반환해야 함
• 정답 오차 허용: 10^-5 이내

2. 종료 상태 정의

게임이 끝나는 경우는 3가지입니다.

1. A 먼저 소진 → 성공 → 확률 1.0
2. B 먼저 소진 → 실패 → 확률 0.0
3. A, B 동시에 소진 → 절반만 성공 인정 → 확률 0.5

이를 코드로 표현하면:

if (a <= 0 && b <= 0) return 0.5;
if (a <= 0) return 1.0;
if (b <= 0) return 0.0;

3. 상태 공간 축소 — 25 단위로 변환

문제에서 모든 감소량이 25의 배수이므로,
n을 25로 나눠서 상태를 줄여도 결과는 동일합니다.

예:
n = 100 → ceil(100 / 25) = 4
즉, (100, 100)mL를 (4, 4)로 변환해 계산

이렇게 하면 상태 수가 획기적으로 줄어듭니다.
예:
n = 5000이면 25단위로는 (200, 200) 상태만 계산하면 됨.

 

4. 점화식 설계

dp(a, b) = A가 a단위, B가 b단위 남았을 때
A가 먼저 소진되거나 동시 소진(0.5)할 확률.

dp(a, b) = 0.25 * (
    dp(a-4, b)   + // A-100, B-0
    dp(a-3, b-1) + // A-75, B-25
    dp(a-2, b-2) + // A-50, B-50
    dp(a-1, b-3)   // A-25, B-75
)

5. 최적화

• n이 매우 크면 (n >= 5000) → 기대값이 1.0에 수렴
  → 바로 1.0 반환
• Memoization(메모이제이션) 사용해 중복 계산 제거

6. 자바 풀이 코드

import java.util.*;

public class SoupServings {

    private static final int FAST_RETURN_THRESHOLD = 5000;

    // 25mL 단위 전이 (A 감소, B 감소)
    private static final int[][] MOVES = {
        {4, 0}, {3, 1}, {2, 2}, {1, 3}
    };

    public double soupServings(int n) {
        if (n <= 0) return 0.5;
        if (n >= FAST_RETURN_THRESHOLD) return 1.0;

        int scaled = (n + 24) / 25; // ceil(n / 25)
        double[][] memo = new double[scaled + 1][scaled + 1];
        for (double[] row : memo) Arrays.fill(row, -1.0);

        return dp(scaled, scaled, memo);
    }

    private double dp(int a, int b, double[][] memo) {
        if (a <= 0 && b <= 0) return 0.5;
        if (a <= 0) return 1.0;
        if (b <= 0) return 0.0;

        if (memo[a][b] >= 0) return memo[a][b];

        double p = 0.0;
        for (int[] mv : MOVES) {
            p += dp(a - mv[0], b - mv[1], memo);
        }
        return memo[a][b] = 0.25 * p; // 4가지 경우 동일 확률
    }

    public static void main(String[] args) {
        SoupServings s = new SoupServings();
        System.out.printf("n=50   -> %.5f\n",  s.soupServings(50));   // 0.62500
        System.out.printf("n=100  -> %.5f\n",  s.soupServings(100));  // 0.71875
        System.out.printf("n=660  -> %.5f\n",  s.soupServings(660));  // ≈0.97644
        System.out.printf("n=5000 -> %.5f\n",  s.soupServings(5000)); // 1.00000
    }
}

7. 실행 결과

n=50   -> 0.62500
n=100  -> 0.71875
n=660  -> 0.97644
n=5000 -> 1.00000

8. 결론

• 이 문제는 **확률 + 동적계획법(DP)**을 결합한 전형적인 상태 전이 문제.
• 핵심 포인트:
  1. 종료 조건을 명확히 정의 (A 먼저 소진 / B 먼저 소진 / 동시 소진)
  2. 모든 감소량이 25 배수이므로 상태 축소
  3. 동일 확률(0.25)로 전이 → 평균값 계산
• n이 커질수록 값은 1.0에 수렴 → 대형 입력 최적화 가능