[Leetcode] 799. Champagne Tower

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

---

DP로 풀었다.

dp[row][glass] = row 행의 glass 번째 그릇의 남는 샴페인 양.

                          = (dp[row-1][glass] + dp[row-1][glass+1]) % 1

dp[0][0] = poured로 갱신 후 아래 수도코드를 진행한다.

for(int row=0; row<=query_row; row++) {
    for(int glass=0; glass<=row; glass++){
        double now = dp[row][glass];
        
        if(now < 1) continue; // 흘러보낼 샴페인이 없는 경우
        // 흘러보낼 샴페인의 반을 다음 glass에 더한다
        dp[row+1][glass] += (now - 1) / 2L; 
        dp[row+1][glass + 1] += (now - 1) / 2L;
        dp[row][glass] = 1L; // 남은 샴페인은 1
    }
}

모든 for 문을 돌았을 때 dp[row][glass]가 정답이 된다.

 

시간복잡도는 N = query_row 일 때, O(N^2).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/799.%20Champagne%20Tower.cpp