2024. 6. 1. 20:28ㆍIT/BaekJoon
문제 링크
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문을 종료하도록 유도하였다.
'IT > BaekJoon' 카테고리의 다른 글
[BAEKJOON] 백준 1431: 시리얼 번호 (C#) (0) | 2024.06.02 |
---|---|
[BAEKJOON] 백준 1270: 전쟁 - 땅따먹기 (C#) (0) | 2024.06.01 |
[BAEKJOON] 백준 1072: 게임 (C#) (0) | 2024.06.01 |
[BAEKJOON] 백준 1063: 킹 (C#) (0) | 2024.06.01 |
[BAEKJOON] 백준 1002: 터렛 (C#) (0) | 2024.05.31 |