[LeetCode] 808. Soup Servings

Chobby·2026년 9월 29일

JavaScript js ts typescript 기술 기초 면접 문제 알고리즘 연습 이직 코딩 코테 테스트 풀이 프로그래밍

LeetCode

목록 보기

1152/1157

문제 요약

A, B 두 수프가 각각 nml씩 있다. 매 턴 아래 4가지 중 하나를 각각 1/4 확률로 골라 퍼낸다.

A 100ml, B 0ml
A 75ml, B 25ml
A 50ml, B 50ml
A 25ml, B 75ml

남은 양보다 많이 퍼야 하면 남은 만큼만 퍼낸다. 둘 중 하나라도 바닥나면 끝이다.

구하는 값은 "A가 먼저 바닥날 확률 + 둘이 동시에 바닥날 확률 × 0.5"이다.
정답과 10⁻⁵ 이내로 차이 나면 정답으로 인정한다.

첫 번째 시도와 실수

처음에는 모든 경우를 끝까지 가 보면서 이긴 횟수를 셌다.

function soupServings(n: number): number {
    let win = 0;
    let draw = 0;
    const dfs = (remainA: number, remainB: number) => {
        if (remainA <= 0) {
            if (remainB > 0) win++;
            else draw++;
            return;
        }
        dfs(remainA - 100, remainB);
        dfs(remainA - 75, remainB - 25);
        dfs(remainA - 50, remainB - 50);
        dfs(remainA - 25, remainB - 75);
    };
    dfs(n, n);
    const games = win + draw;
    return win / games + (draw / games) * 0.5;
}

이 풀이에는 실수가 세 가지 있다.

실수 1. 경우의 수를 셌다 (핵심)

동전으로 예를 들어 보자.

앞면이면 바로 승리. 뒷면이면 한 번 더 던져서 앞면이면 승리, 뒷면이면 패배.

앞 → 승리 (확률 1/2)
뒤 → 앞 → 승리 (확률 1/4)
뒤 → 뒤 → 패배 (확률 1/4)

개수로 세면 승리 2개, 패배 1개라서 2/3이다.
실제 확률은 1/2 + 1/4 = 3/4이다.

한 단계 더 들어갈 때마다 확률이 쪼개지므로 짧게 끝나는 경로일수록 일어날 확률이 크다. 이 문제도 한 턴마다 1/4씩 곱해지는데, win++는 모든 경로를 똑같이 1개로 센다.

실수 2. B가 먼저 바닥나도 멈추지 않았다

B가 먼저 바닥나면 0점이고 게임은 거기서 끝이다. 그런데 A만 검사했기 때문에 B가 음수인 채로 계속 퍼내다가, A까지 바닥나면 무승부(0.5점)로 잘못 계산했다.

실수 3. 너무 느리다

한 번 호출할 때마다 4갈래로 갈라져서 호출 수가 4ⁿ 꼴로 늘어난다. n은 최대 10⁹이다.

개선 1. 확률을 반환하는 DFS + 메모이제이션

dfs(a, b)가 "A가 a, B가 b만큼 남았을 때 구하는 확률"을 반환하도록 바꾼다.

종료 상태에서 반환할 값은 명확하다. 동시에 바닥나면 0.5, A가 먼저면 1, B가 먼저면 0이다.
그 밖의 상태는 네 가지 다음 상태의 확률에 각각 1/4를 곱해 더한다.
같은 (a, b) 상태가 여러 번 나오므로 결과를 cache에 저장해 재사용한다.
퍼내는 양이 전부 25의 배수라서 25ml를 1칸으로 보면 숫자가 작아진다. Math.ceil(n / 25)로 변환하고, 퍼내는 양도 4, 3, 2, 1칸이 된다.

그런데 이렇게만 하면 n = 10⁹일 때 m = 4천만이 되어 Maximum call stack size exceeded가 난다. 캐시가 비어 있는 상태에서 재귀가 수천만 단계 깊이로 들어가기 때문이다.

개선 2. n이 크면 답은 사실상 1이다

한 턴에 퍼내는 양의 평균을 보면 이렇다.

A: (100 + 75 + 50 + 25) / 4 = 62.5ml
B: (0 + 25 + 50 + 75) / 4 = 37.5ml

A가 평균적으로 훨씬 빨리 줄어든다. 수프가 적을 때는 운이 크게 작용하지만, 많아질수록 턴 수가 늘어나서 운이 평균에 묻힌다. 그래서 n이 커질수록 확률은 1에 수렴한다.

문제는 10⁻⁵ 오차를 허용하므로, 확률이 0.99999를 넘는 순간부터는 그냥 1을 반환해도 정답이다. 흔히 보이는 if (n > 4800) return 1이 이 원리이고, 4800은 직접 계산해서 찾은 경계값이다.

매직 넘버를 외우는 대신 코드가 직접 확인하게 할 수도 있다.

for (let k = 1; k < m; k++) {
    if (dfs(k, k) > 1 - 1e-5) return 1;
}

수프 양을 1칸, 2칸, 3칸… 순서로 늘려 가며 확률을 확인하다가 0.99999를 넘으면 바로 1을 반환한다. 약 190칸(약 4,800ml) 근처에서 넘기 때문에 m이 4천만이어도 금방 끝난다.

이 방식은 스택 오버플로도 함께 해결한다. 작은 k부터 계산하면 결과가 cache에 쌓이므로, 다음 k를 계산할 때는 몇 단계만 새로 들어가면 된다.

최종 코드

function soupServings(n: number): number {
    const cache = new Map<string, number>();
    const m = Math.ceil(n / 25);

    const dfs = (remainA: number, remainB: number): number => {
        if (remainA <= 0 && remainB <= 0) return 0.5;
        if (remainA <= 0) return 1;
        if (remainB <= 0) return 0;

        const key = `${remainA},${remainB}`;
        if (cache.has(key)) return cache.get(key)!;

        const probability =
            0.25 *
            (dfs(remainA - 4, remainB) +
                dfs(remainA - 3, remainB - 1) +
                dfs(remainA - 2, remainB - 2) +
                dfs(remainA - 1, remainB - 3));
        cache.set(key, probability);
        return probability;
    };

    for (let k = 1; k < m; k++) {
        if (dfs(k, k) > 1 - 1e-5) return 1;
    }
    return dfs(m, m);
}