BOJ_1166 : 선물

👉 문제링크

1166번: 선물

---

---

🔸 문제 분석 🔸

• 한 변의 길이가 A인 N개의 정사각형 상자가 있다.
• L * W * H 크기의 상자에 상자를 모두 넣어야 할 때, A의 최대값을 출력한다.
  • 특정 값을 찾는 방법으로 이분탐색을 사용한다.
  • 문제 조건의 절대/상대 오차는 10^-9 까지 허용이므로 충분한 반복횟수로 이분탐색을 진행한다.

🔸 코드 🔸

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int l = sc.nextInt();
        int w = sc.nextInt();
        int h = sc.nextInt();

        double start = 0, end = Math.max(l, Math.max(w,h));

        for (int i = 0; i < 10000; i++) {
            double mid = (start + end) / 2;
            if ((long)(l/mid) * (long)(w/mid) * (long)(h/mid) >= n)
                start = mid;
            else
                end = mid;
        }
        System.out.println(end);
    }
}

🔸 코드 해석 🔸

• n, l, w, h는 최대 10억이므로 int형으로 선언한다.
• 이분탐색을 진행하기 위해 처음 인덱스와 끝 인덱스를 지정한다.
  • 소수점까지 계산되어야 하므로 double형으로 계산한다.
• start와 end의 차이가 10^-9보다 더 작아지도록 충분히 반복한다.
  • start와 end의 중간값을 A로 두고, l * w * h 크기의 상자에 들어가는지 확인한다.
  • 들어간다면 start는 mid, 들어가지 않는다면 end를 mid로 바꾸고 다시 반복한다.
• start혹은 end를 출력한다.

---

🔸 end 🔸

• 스페셜저지인 이유는 오차범위 안에서 답을 도출하면 되기 때문인 것 같다.
• 이전 포스팅과 같이 이분탐색의 파라메트릭 서치 문제인 것 같다.
  • 이진탐색과 파라메트릭 서치를 완전히 같게 보았지만, 포스팅을 찾아보니 알고리즘은 같아도 찾고자하는 값에서 차이가 나는 것 같다.
  • 이진탐색 : 정렬된 일련의 값에서 원하는 값을 찾는 알고리즘
  • 파라메트릭 서치 : 일련의 값들이 아니라 주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘