[LeetCode] 799. Champagne Tower

문제

1, 2, 3, ... 개씩 늘어나는 피라미드 형태로 잔을 쌓고 맨 위 잔에 poured컵을 붓는다. 잔은 1컵까지만 담을 수 있고, 넘친 양은 바로 아래 왼쪽·오른쪽 잔에 반씩 떨어진다. query_row행 query_glass번째 잔이 얼마나 찼는지 구한다.

핵심 아이디어

잔을 "채운다"고 생각하지 말고, 각 잔에 도착한 액체의 총량을 한 줄씩 아래로 흘려보낸다.

• 잔 (i, j)에 x컵이 도착하면 넘치는 양은 x - 1
• 그 절반인 (x - 1) / 2가 (i+1, j)와 (i+1, j+1)에 각각 더해진다
• 가운데 잔은 부모가 둘이라 두 번 더해진다

poured = 4일 때:

row 0:        [ 4 ]          excess = (4 - 1) / 2 = 1.5
             ↙     ↘
row 1:    [1.5]   [1.5]      excess = (1.5 - 1) / 2 = 0.25
          ↙   ↘   ↙   ↘
row 2: [0.25] [0.5] [0.25]

배열에 담긴 값은 "도착한 총량"이므로 1을 넘을 수 있다. 중간에 자르면 아래로 흘릴 양을 계산할 수 없으니, 답을 낼 때만 min(1, 값)으로 자른다.

코드

function champagneTower(poured: number, query_row: number, query_glass: number): number {
  let row = [poured];

  for (let i = 0; i < query_row; i++) {
    const next = Array(i + 2).fill(0);
    for (let j = 0; j <= i; j++) {
      const excess = (row[j] - 1) / 2;
      if (excess > 0) {
        next[j] += excess;
        next[j + 1] += excess;
      }
    }
    row = next;
  }

  return Math.min(1, row[query_glass]);
}

이전 줄은 다음 줄을 만들고 나면 필요 없으므로 배열 하나만 재사용한다.

• 시간: O(query_row²)
• 공간: O(query_row)

삽질

if (excess > 1)로 잘못 써서 166/195에서 막혔다. poured = 2면 넘친 1컵이 반씩 나뉘어 excess = 0.5인데, 0.5 > 1이 거짓이라 아래로 아무것도 흐르지 않았다. 조건의 의미는 "넘쳤는가"이므로 excess > 0이 맞다. 넘친 양이 큰 케이스에서는 두 조건이 같은 결과를 내기 때문에 대부분의 테스트를 통과해서 원인을 늦게 찾았다.