799. Champagne Tower

• 문제에서 설명된 대로 첫번째 잔 부터 부어진 샴페인 숫자를 기준으로 넘친 양을 계산해서 다음잔의 샴페인 양을 계산해나가면 된다.
• 계산 안하고 할 수 있는 방법이 있나 고민해봤는데 별로 떠오르는 방법이 없는것 같다.

• query_row = R 이라고 할 때 해당되는 row의 샴페인 잔의 상태를 계산하려면 다음 row까지 있어야 하므로 총 (R + 1) * (R + 2) / 2 개의 잔이 필요하다.
• R + 1 row의 샴페인 양은 설사 넘쳤다고 하더라도 쿼리 대상이 아니므로 굳이 계산할 필요가 없다.

• 어떤 잔의 와인 양을 G(r, c) 라고 할 때
• G(r, c) ≤ 1.0 인 경우에는 넘치지 않았으므로 아무 것도 하지 않는다.
• G(r, c) > 1.0 인 경우에는 넘친 양 G(r, c) - 1.0 을 반으로 나누어 각각 그 아래에 있는 두 잔 G(r + 1, c), G(r + 1, c + 1) 에 분배한다.

class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        vector<double> glass((query_row + 2) * (query_row + 3) / 2);
        glass[0] += poured;
        int row_start = 0;
        for (int row = 0; row <= query_row; ++row) {
            bool found_excess = false;
            int next_row_start = row_start + row + 1;
            for (int col = 0; col <= row; ++col) {
                double excess = glass[row_start + col] - 1.0;
                if (excess <= 0.0) continue;
                found_excess = true;
                glass[next_row_start + col] += excess / 2.0;
                glass[next_row_start + col + 1] += excess / 2.0;
                glass[row_start + col] = 1.0;
            }
            if (!found_excess) break;
            row_start = next_row_start;
        }
        row_start = query_row * (query_row + 1) / 2;
        return glass[row_start + query_glass];
    }
};

• 메모리 공간을 좀 더 아끼고 싶다면 아래처럼 row를 2개 정의하고 toggle 하여 사용하는 방법도 있다.

class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        vector<double> cur_row(query_row + 2);
        vector<double> next_row(query_row + 2);
        next_row[0] += poured;
        int last_row = 0;
        for (int row = 0; row <= query_row; ++row) {
            cur_row.swap(next_row);
            fill(next_row.begin(), next_row.begin() + row + 1, 0);
            bool found_excess = false;
            for (int col = 0; col <= row; ++col) {
                double excess = cur_row[col] - 1.0;
                if (excess <= 0.0) continue;
                found_excess = true;
                next_row[col] += excess / 2.0;
                next_row[col + 1] += excess / 2.0;
                cur_row[col] = 1.0;
            }
            last_row = row;
            if (!found_excess) break;
        }
        return last_row == query_row
            ? cur_row[query_glass] : 0.0;
    }
};