백준 1166 - 선물 (자바 - 이분탐색)

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

1166번: 선물

 

* 문제 요약

민식이는 아이들에게 선물할 같은 크기의 작은 박스를 N개 가지고 있다. 모든 작은 박스는 정육면체이고, 크기는 A x A x A 이다.

민식이는 이 작은 박스를 크기가 L x W x 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

 

* 예시

 

* 해결 과정

입력받은 L, W, H 중 가장 작은 값을 정육면체의 한 변이 가질 수 있는 최대값(end) 으로 설정해준다. 큰 박스 안에 작은 박스 하나만 넣는 경우가 있다고 했을 때, 직육면체의 한 변이라도 정육면체의 변 길이보다 작다면 작은 박스의 일부분이 큰 박스 바깥으로 벗어나게 되기 때문이다.

최소한 직육면체에서 가장 짧은 변의 길이와 정육면체의 길이를 딱 맞춰야 하기 때문에 L, W, H 중 가장 짧은 길이를 정육면체가 가질 수 있는 변의 길이중 최대값으로 설정해준다.

 

소수점 까지 최대한 정확하게 계산해줘야 하는 문제의 경우 단순히 start <= end 같은 조건이 아닌, 1만번 정도의 충분히 많은 반복을 통해 찾고자 하는 값의 범위를 최대한 정밀하게 줄여주는 것이 좋다.

이분 탐색을 할 경우 다음과 같은 로직을 따른다.

1. (start + end) / 2 값을 mid 에 저장해준다. 이 때 mid 는 현재 반복에서 정육면체 한 변의 길이에 해당된다.

2. 각 변마다 들어갈 수 있는 최소 갯수의 곱으로 (width / mid : 가로 변 기준 정육면체가 최대로 들어갈 수 있는 갯수), (vertical / mid : 세로 변 기준 정육면체가 최대로 들어갈 수 있는 갯수), (height / mid : 높이 값을 기준으로 정육면체가 최대로 들어갈 수 있는 갯수) 주어진 선물 상자보다 더 많은 양이 들어가는 경우, start = mid 값으로 초기화 하여 mid 값이 더 큰쪽으로 범위를 좁혀준다.

3. 그렇지 않을 경우 end = mid 값으로 초기화 하여 mid 값이 더 작은 쪽으로 범위를 줄여준다.

4. 반복문이 끝난 후 start 를 출력시켜 준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] inputArray = br.readLine().split(" ");

        int giftCount = Integer.parseInt(inputArray[0]);
        int width = Integer.parseInt(inputArray[1]);
        int vertical = Integer.parseInt(inputArray[2]);
        int height = Integer.parseInt(inputArray[3]);
        int[] box = new int[3];

        box[0] = width;
        box[1] = vertical;
        box[2] = height;

        Arrays.sort(box);
        // N 개의 정육면체를 직육면체에 모두 넣을 수 있음과 동시에, 정육면체가 가질수 있는 한 변 길이의 최대값을 구해야 함
        double start = 0;
        double end = box[0];

        // 정육면체 한 변의 길이가 길어 봤자 높이값을 넘지 못함
        for(int i = 0; i < 10000; i++) {
            double mid = (start + end) / 2;
            // 각 변마다 들어갈수 있는 최소 갯수의 곱 으로 주어진 선물 상자보다 더 많은 양이 들어가는 경우
            if((long)(width/mid) * (long)(vertical/mid) * (long)(height/mid) >= giftCount){
                start = mid;
            }
            else{
                end = mid;
            }
            
        }
        bw.write(start + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

직육면체 (큰 박스) 의 각 변마다 들어갈 수 있는 작은 박스 최소 갯수의 곱으로 주어진 선물 상자보다 더 많은 양이 들어가는 경우와 그렇지 않은 경우로 나누어 범위를 정밀하게 좁혀가며 답을 찾았으므로 이분탐색 문제에 해당된다.