Champagne

Code

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

https://community.topcoder.com/stat?c=problem_solution&cr=270505&rd=4472&pm=1525