[BOJ] 1166 선물 - JAVA

1. 문제

1166번: 선물

민식이는 아이들에게 선물할 같은 크기의 작은 박스를 N개 가지고 있다. 모든 작은 박스는 정육면체이고, 크기는 A × A × A 이다. 민식이는 이 작은 박스를 크기가 L × W × H 인 직육면체 박스에 모두 넣으려고 한다. 모든 작은 박스는 큰 박스 안에 있어야 하고, 작은 박스의 변은 큰 박스의 변과 평행해야 한다.
N, L, W, H가 주어질 때, 가능한 A의 최댓값을 찾는 프로그램을 작성하시오.

---

2. 풀이

1.  최소는 0, 최대는 L,W,H중 최소값으로 설정한다.

2.  다른 이분탐색과 다르게 high=mid-1, low=mid+1이 아니라 high=mid, low=mid로 변경한다.

3.  따라서 무한반복을 방지하기 위해 high==mid이거나 low==mid일 때 while 반복문을 중단한다.

import java.io.*;
import java.util.*;

public class BOJ_1166_선물 {
   public static void main(String[] args) throws IOException {
      StringTokenizer st = new StringTokenizer(new BufferedReader(new InputStreamReader(System.in)).readLine());
      int N = Integer.parseInt(st.nextToken());
      int L = Integer.parseInt(st.nextToken());
      int W = Integer.parseInt(st.nextToken());
      int H = Integer.parseInt(st.nextToken());

      double low = 0;
      double high = Math.min(L,Math.min(W,H));
      double mid;
      while(low<high){
         mid = (low+high)/2;

         if((long)(L/mid)*(long)(W/mid)*(long)(H/mid)<N){
            if(high==mid) break;
            high = mid;
         }else{
            if(low==mid) break;
            low = mid;
         }
      }
      System.out.println(low);
   }
}

---

3. 결과