[BAEKJOON] 백준 1166: 선물 (C#)

문제 링크

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

 

 

문제

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

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

 

 

입력

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

 

 

출력

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

 

 

제한

• 1 ≤ N ≤ 1,000,000,000
• 1 ≤ L, W, H ≤ 1,000,000,000

 

 

 

통과한 답안

namespace _1166
{
    internal class Program
    {
        static void Main(string[] args)
        {
            double[] inputs = Console.ReadLine().Split(' ').Select(double.Parse).ToArray();

            double N = inputs[0];
            double L = inputs[1];
            double W = inputs[2];
            double H = inputs[3];

            double low = 0;
            double high = Math.Min(L, Math.Min(W, H));
            double mid = 0;
            int cnt = 0;

            while (high - low > 1e-9)
            {
                mid = (low + high) / 2;
                if (CanFit(mid, N, L, W, H))
                {
                    low = mid;
                }
                else
                {
                    high = mid;
                }

                cnt++;

                if (cnt > 1000000)
                    break;
            }

            Console.WriteLine(low);
        }

        static bool CanFit(double side, double N, double L, double W, double H)
        {
            long countL = (long)(L / side);
            long countW = (long)(W / side);
            long countH = (long)(H / side);

            return (double)countL * countW * countH >= N;
        }
    }
}

 

큰 상자의 가로, 세로, 높이가 주어졌을 때,

그 상자 안에 정육면체를 N개 넣으려는 경우,

정육면체의 한 변의 최대 길이를 찾는 문제이다.

 

이는 이분 탐색을 이용하여 해결할 수 있는 문제로,

한 변의 최솟값(low)은 0부터, 최댓값(high)은 큰 상자의 가장 작은 변의 길이부터 시작하여

중간값(mid)를 설정한 뒤에 이 값을 이용하여 정육면체를 만들었을 때,

N개가 들어가는지 확인한다. 이를 10의 -9제곱(1e-9)까지 계산하는데 

while문을 이용하면 시간 초과가 발생하는 문제가 생긴다.

또, 계산을 -7제곱이나 -8제곱까지 계산하면 오차의 문제로 틀리게 된다.

 

이를 해결하기 위해서 연산 횟수 cnt를 추가한 뒤에

시간 초과가 발생하지 않는 범위에서 while문을 종료하도록 유도하였다.