Leetcode 799. Champagne Tower

문제

We stack glasses in a pyramid, 
where the first row has 1 glass, 
the second row has 2 glasses, and so on until the 100th row.  Each glass holds one cup of champagne.
After four cups of champagne are poured, 
the third row has the middle glass half full, 
and the two outside glasses are a quarter full, as pictured below.

위와 같이 생긴 샴페인 잔의 탑이 100층이 있습니다.
각각의 샴페인은 1의 양을 담을수 있고, 그 이상은 양 옆으로 흘러 내립니다.
흘러내리는 양은 정확히 절반씩입니다.
맨 위에 poured 만큼을 흘려 보냈을떄
query_row 번째 줄, query_glass 번째 샴페인 잔에 얼마가 들어 있는지 적으시오
참고로 주어진 줄과 번째는 0-index 입니다.

예시

Input: poured = 2, query_row = 1, query_glass = 1
Output: 0.50000
Explanation: 2만큼 흘려 보낼시 0.5만큼 흘러 0.5가 된다.

풀이

• 윗잔에 100 만큼 흘려보낸다면 1만큼 받고 아래 두 잔에 (100 - 1) / 2 만큼 흘려 보낸다.

이것을 이용한다면 쉽게 풀수 있다.
윗잔부터 계산해 아래에 흘려보낸만큼 더해준다.
그 후 잔의 값을 리턴한다.
단, 이 경우는 1보다 큰 값이 있을수 있는데, min(1.0, 잔의 값) 을 리턴해 줌으로 방지한다.

코드

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        glasses = [ [0 for y in range(x + 1)] for x in range(query_row + 1)]

        glasses[0][0] = poured

        for i in range(query_row):
            for j in range(i + 1):
                if glasses[i][j] > 1.0 : 
                    exceed = (glasses[i][j]-1) / 2
                    glasses[i+1][j] += exceed
                    glasses[i+1][j+1] += exceed

        return min(1.0, glasses[query_row][query_glass])