[leetcode/JS] 808_Soup Servings 풀이

🎲 문제

808. Soup Servings

Medium

---

수프에는 유형 A와 유형 B의 두 가지 유형이 있습니다. 처음에는 각 유형의 수프가 n ml입니다. 작업에는 네 가지 종류가 있습니다.

1. 수프 A 100ml와 수프 B 0ml를 제공
2. 수프 A 75ml와 수프 B 25ml 제공
3. 수프 A 50ml와 수프 B 50ml를 제공
4. 수프 A 25ml와 수프 B 75ml를 제공

우리가 수프를 대접할 때, 우리는 그것을 누군가에게 주고, 우리는 더 이상 그것을 가지고 있지 않습니다. 매 턴, 우리는 0.25의 동일한 확률로 네 가지 작업 중에서 선택합니다. 남은 수프의 양이 작업을 완료하기에 충분하지 않은 경우 가능한 한 많이 제공됩니다. 우리는 더 이상 두 가지 유형의 수프가 모두 부족하면 중단합니다.

B 수프 100ml를 모두 먼저 사용하는 작업은 없습니다.
수프 A가 먼저 비게 될 확률과 A와 B가 동시에 비게 될 확률의 절반을 반환합니다. 실제 답변의 10-5 이내의 답변이 수락됩니다.

 

There are two types of soup: type A and type B. Initially, we have n ml of each type of soup. There are four kinds of operations:

1. Serve 100 ml of soup A and 0 ml of soup B,
2. Serve 75 ml of soup A and 25 ml of soup B,
3. Serve 50 ml of soup A and 50 ml of soup B, and
4. Serve 25 ml of soup A and 75 ml of soup B.

When we serve some soup, we give it to someone, and we no longer have it. Each turn, we will choose from the four operations with an equal probability 0.25. If the remaining volume of soup is not enough to complete the operation, we will serve as much as possible. We stop once we no longer have some quantity of both types of soup.

Note that we do not have an operation where all 100 ml's of soup B are used first.

Return the probability that soup A will be empty first, plus half the probability that A and B become empty at the same time. Answers within 10-5 of the actual answer will be accepted.

 

  

Example 1:

 

Input: n = 50
Output: 0.62500
Explanation: If we choose the first two operations, A will become empty first.
For the third operation, A and B will become empty at the same time.
For the fourth operation, B will become empty first.
So the total probability of A becoming empty first plus half the probability that A and B become empty at the same time, is 0.25 * (1 + 1 + 0.5 + 0) = 0.625.

Example 2:

Input: n = 100
Output: 0.71875

 

Constraints:

• 0 <= n <= 109

 

---

💡 접근 방법

메모리 복잡성에 대한 이해와 재귀 활용이 부족하여 아래 링크의 설명과 코드(c++, java, python)를 첨부함

https://leetcode.com/problems/soup-servings/solutions/121711/c-java-python-when-n-4800-just-return-1/?orderBy=hot 

 

/**
 * @param {number} n
 * @return {number}
 */
var soupServings = function (n) {
  if (n > 4800) return 1;

  const memo = new Map();

  const prob = (a, b) => {
    const key = a + ',' + b;
    
    if (memo.has(key)) return memo.get(key);
    if (a === 0 && b !== 0) return 1;
    if (a === 0 && b === 0) return 0.5;
    if (a !== 0 && b === 0) return 0;

    let p = prob(100 > a ? 0 : (a - 100), b) +
      prob(75 > a ? 0 : (a - 75), 25 > b ? 0 : (b - 25)) +
      prob(50 > a ? 0 : (a - 50), 50 > b ? 0 : (b - 50)) +
      prob(25 > a ? 0 : (a - 25), 75 > b ? 0 : (b - 75));

    p *= 0.25;
    memo.set(key, p);

    return p;
  }
  return prob(n, n);
};

 

---

 

📖 후기

풀이 실패했다. 확률과 통계, 재귀 구조는 아직 직접 구현하기 어려움을 느낀다. 🥴 

부족함을 채워 leetcode 디스커션에 있는 해석들 처럼 풀이가 가능하길 바란다.