[백준_1166번] 선물

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

1166번: 선물

[문제]

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

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

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_1166 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		long n=sc.nextInt();
		long l=sc.nextInt();
		long w=sc.nextInt();
		long h=sc.nextInt();
		
		double start=0;
		double end=Math.max(l,Math.max(w, h));
		
		// 이분탐색
		for(int i=0;i<10000;i++) {
			double mid=(start+end)/2; // 정육면체의 한 변의 길이
			
			// 직육면체에 들어갈 수 있는 정육면체의 개수 구해 n과 비교
			if((long)(l/mid)*(long)(w/mid)*(long)(h/mid)>=n)
				start=mid;
			else
				end=mid;
		}
		System.out.println(start);
	}

}

 

[고찰]

 이번 문제는 이분탐색 문제로 정육면체가 될 수 있는 한 변의 길이를 가정하고, 해당 길이일 경우 직육면체에 들어갈 수 있는 개수를 구해 n과 비교해 변의 길이를 조정해나가는 방식으로 해결할 수 있다. 

 이전 스터디 문제로 선정되었지만 풀지 않고 넘어가 다시 풀어보는 시간을 가졌다.