PostAddsense


Champagne Topcoder



public class Champagne
{
    public String howMuch(int height, int glass, int units) {
        int B = 1 << height-1;
        int i=0,j=0,n,d;
        int[][] amount = new int[21][21];

        amount[0][0] = units*B;

        loop:
        for (i=0; i <= height; i++) {
            for (j=0; j <= i; j++) {
                int f = amount[i][j]-2*B;
                if(f > 0) {
                    amount[i+1][j] += f/2;
                    amount[i+1][j+1] += f/2;
                    amount[i][j] = 2*B;
                }
                glass--;
                if(glass == 0) break loop;
            }
        }

        n = amount[i][j];
        d = 2*B;
        if(n==0) return "0/1";
        if(n==d) return "1/1";

        while(n%2==0 && d%2==0) {n/=2; d/=2;}

        return n + "/" + d;
    }
}


Explanation

먼저 amount[0][0] 에 현재 가지고 있는 포도주의 양(units * B)을 대입한다. 여기서 B는 한 잔의 반을 채우는 양이다.
현재 잔(f)에는 amount[i][j] - 2*B에 값을 넣는다. 2*B는 한 잔의 양이다. 남은 포도주가 있다면 (즉, f>0이라면) 밑에 있는 두 개의 잔(i+1,j and i+1,j+1)에는 f/2 즉, 2등분해서 각각 넣어준다.
2*B 를 뺀 나머지를 밑에  두 잔에 넣었으므로 amount[i][j] 에는 2*B가 남아 있게 된다.

n에 최근까지 포도주를 부은 잔(amount[i][j]) 를 넣고, d에 포도주 한 잔 양(2*B)을 넣는다.
n==0 이면 지정한 잔까지 포도주가 채워지지 못했다는 뜻이므로 0/1 을 반환한다. n==d 이면 정확히 한 잔 분량이 들어간 것이므로 1/1 을 반환한다.

while문은 분수를 약분한다.


References