799. Champagne Tower

[zeikar]

Problem link

https://leetcode.com/problems/champagne-tower

Problem Summary

샴페인 잔이 피라미드 형식으로 쌓여있고 맨 위의 잔에 샴페인을 부었을 때 특정 행, 열에 샴페인이 얼마나 차있는지 출력하는 문제.

Solution

처음에 테스트로 직접 한번씩 부었는데 당연히 시간초과가 난다.
수학적으로 가능한가 싶었는데 그냥 돌려주면 된다. 단 한번씩 붓는게 아니고 처음에 전부 부어주었다고 가정하면 된다. 넘치는 양을 다음 잔에 부어주면서 죽 돌려주면 된다.

시간복잡도는 O(N^2)

Source Code

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        glass = [[0] * 101 for i in range(101)]
        glass[0][0] = poured

        for i in range(query_row + 1):
            for j in range(i + 1):
                if glass[i][j] >= 1:
                    glass[i + 1][j] += (glass[i][j] - 1) * 0.5
                    glass[i + 1][j + 1] += (glass[i][j] - 1) * 0.5

                glass[i][j] = min(1, glass[i][j])

        return glass[query_row][query_glass]