[백준] 1166번 : 선물 (C++)

1166번 : 선물

---

문제)

민식이는 아이들에게 선물할 같은 크기의 작은 박스를 N개 가지고 있다. 모든 작은 박스는 정육면체이고, 크기는 A × A × A 이다. 민식이는 이 작은 박스를 크기가 L × W × H 인 직육면체 박스에 모두 넣으려고 한다. 모든 작은 박스는 큰 박스 안에 있어야 하고, 작은 박스의 변은 큰 박스의 변과 평행해야 한다.

N, L, W, H가 주어질 때, 가능한 A의 최댓값을 찾는 프로그램을 작성하시오.

 

 

 

입력 :

첫째 줄에 네 정수 N, L, W, H가 주어진다.

 

 

 

출력 :

첫째 줄에 가능한 A의 최댓값을 출력한다. 절대/상대 오차는 10^-9까지 허용한다.

 

 

 

 

 

풀이)

 

// 1166. 선물
#include <iostream>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
int n, l, w, h;
 
bool check(long double mid)
{
    // mid값으로 계산할 경우,
    // 문제에서 제공한 직사각형에 넣을 수 있는 
    // 정사각형의 갯수를 구한다.
 
    // 각 l w h가 최대 10억이므로, long long으로 계산해야한다.
    long long _a = l / mid;
    long long _b = w / mid;
    long long _c = h / mid;
 
    long long cnt = _a * _b * _c;
 
    if (cnt >= n) return true;
    else return false;
}
 
 
int main()
{
    cin >> n >> l >> w >> h;
 
    long double s = 0;
    long double e = min(l, min(w, h));
 
    long double answer;
 
    int cnt = 0;
    while (s <= e)
    {
        // 여유롭게 150번 이진탐색을 진행한다.
        // 소수점 계산이기 때문에 제한을 걸어둠.
        if (cnt == 150) break;
 
        long double mid = (s + e) / 2;
 
        if (check(mid))
        {
            s = mid;
            answer = mid;
        }
        else
        {
            e = mid;
        }
        cnt++;
    }
 
    // 출력할 정밀도를 늘려준다.
    cout.precision(30);
    cout << answer;
 
 
    return 0;
}
 

 

---

출처 : https://www.acmicpc.net/problem/1166 

1166번: 선물