백준 11390: 맛있는 과자

https://www.acmicpc.net/problem/11390

11390번: 맛있는 과자

 
DP문제를 돌다가 발견했는데 알고보니 그냥 수학문제. DP인 이유는 조합을 이용하기 때문이다.
 
STEP 0.
DP를 이용해 nCk (조합, Combination) 값들을 전부 배열 co[n][k]에 저장해준다.
 
STEP 1.

사진 출처: https://www.acmicpc.net/problem/11390

두 삼각형의 넓이비는 a^2 : b^2. 왜 그런지는 중학교 때 배운다.
a와 b를 입력받는데, a가 b보다 더 큰 값이라고 가정해보자. 어차피 입력받은 뒤 작은 게 a가 되도록 수정하면 되니 상관 X.
 
A=a^2;
B=b^2;
라고 둔다.
즉, 두 삼각형의 넓이비는 A:B이다.
 
한 번 더 나눈다면?
네 삼각형의 넓이비는 A^2 : AB : AB : B^2, 전체 넓이는 이항정리에 의해 (A+B)^2
또 나누면?
넓이가 A^p*B^(3-p)인 삼각형이 co[3][p]개 있을 것이다.
 
n번 나누면?
넓이가 A^p*B^(n-p)인 삼각형이 co[n][p]개 있을 것이다. (p가 작을수록 A^p*B^(n-p)가 크다.)
 
이건 비율만 생각하고 구한 것이기 때문에 전체 넓이를 (A+B)^n로 가정한 거다.
 
실제 삼각형의 넓이는 A^p*B^(n-p)/(A+B)^n * (a*b*1/2)인 것이다.
 
이제 p만 구하면 된다.
 
n=4인 경우를 예를 들어 보자.
조합은 1 4 6 4 1이다.
이건 X0>X1>X2>X3>.....이라고 할 때
넓이가 X0인 삼각형이 1개 있고
넓이가 X1인 삼각형은 4개 있고
넓이가 X2인 삼각형은 6개 있고 ...
넓이가 Xp인 삼각형인 nCp ( co[n][p] ) 개 있고...
이런 뜻이다.
참고로 Xp= A^p*B^(n-p)/(A+B)^n * (a*b*1/2)일 것이다.
 
그럼 예를들어 k=7이라면 넓이가 7번째로 큰 삼각형의 넓이는 X2일 것이다.
 
즉, k=7일 때 p=2
 
STEP 2.
이런 과정을 통해 p을 구했으니, 이제 log ( A^p*B^(n-p)/(A+B)^n * (a*b*1/2) )를 계산해주면 된다.
이 값은 로그의 성질에 의해 
p * log(A) + (n - p) * log(B) - n * log(A + B) + log(a) + log(b) - log(2)
와 동일하다.
정확도를 높이기 위해 float가 아닌 double형을 사용한다.
 
그리고 소수점 아래 8번째 자리까지 정확도를 판단하니까 소수점 아래 13번째 자리 정도까지 출력하자.
다음은 C언어로 구현한 것이다.

#define MAX 45
typedef long long ll;
 
//STEP 0
ll co[MAX][MAX] = { 0 };//combination
 
void calcom() // MAX C MAX 까지 저장함
{
    co[0][0] = 1;
    for (int i = 1;i < MAX;i++)
    {
        co[i][0] = 1;
        co[i][1] = i;
        co[i][i - 1] = i;
        co[i][i] = 1;
        for (ll j = 1;j < i - 1;j++)
        {
            co[i][j] = co[i - 1][j - 1] + co[i - 1][j];
            //co[i][j] %= DIV;
            //DIV로 나눈 값을 배열에 저장
        }
    }
 
}
 
 
int main()
{
    ll a, b, n, k;
    scanf("%lld %lld %lld %lld", &a, &b, &n, &k);
    calcom();
    
    //STEP 1
    if (a < b)
    {
        ll temp = b;
        b = a;
        a = temp;
    }
   
    ll A = a * a;
    ll B = b * b;
    ll h = 0;
    ll p = 0;
    for (;p < n + 1;p++)
    {
        h += co[n][p];
        if (k <= h)
            break;
    }
    
    //STEP 2
    double x = p * log(A) + (n - p) * log(B) - n * log(A + B) + log(a) + log(b) - log(2);
    printf("%.13f", x);
}