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
최근 덧글