백준 (BOJ) 1166 선물 java

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

1166번: 선물

코드 짜기도 전에 풀이에서 무한 루프에 빠졌던 문제.

 

1. 소수점을 다루고

2. 오차를 허용하는

 

이런 문제는 충분한 반복을 통해 정답과 아주 가까운 근사치를 얻을 수 있다.

 

아래의 코드에서 (long)(L/mid)와 같이 double 계산 후 long을 씌워주는 이유가 있다.

 

예를 들어,

 

채울 수 있는 작은 박스가 1.0이고,

 

담는 상자의 가로 길이가 2.4일 때,

 

결국 1.0으로 채울 수 있는 관점으로 보면 가로 길이는 2로 보는 것과 같은 이치이다.

 

 

 

그리고 이분 탐색은 low와 high를 정해주는 것이 아주 중요한데, (잘못하면 시간 초과 뜬다.)

 

여기서 high를 가로 X 세로 X 높이 중에서 최소의 길이로 정한 이유가 있다. 쉽게 답을 알 수 있다.

 

low는 조금 더 생각해봐야 한다. mid가 나중에 0.xxx의 소수점으로 갈 수 있기 때문에 1로 지정하면 안 된다...

(여기서 많이 틀렸다. =,.=)

 

그 이유는, 1 X 1 X 1의 상자에 10개를 채워넣는다고 생각해보면 금방 알 수 있다.

(사실 나는 금방 알진 못했다. 참고로 답은 0.333333333...이다.)

 

더불어 일반적인 정수를 다루는 이분 탐색 문제와 다르게 이 문제는 double을 다루고 있다.

 

따라서 low와 high를 갱신할 때, 답이 근사치에 가까워지도록 mid 값만을 이용해 폭을 줄여나간다(!).

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        long L = Long.parseLong(st.nextToken());
        long W = Long.parseLong(st.nextToken());
        long H = Long.parseLong(st.nextToken());
        double min = L;
        min = Math.min(min, W);
        min = Math.min(min, H);

        // A(mid)의 최댓값을 구하시오.

        double l = 0;
        double h = min; // A <= 큰 상자의 최소길이
        double mid;

        // 소수점을 다루면서 오차를 허용하는 문제는 이런 식으로 충분한 반복을 통해 아주 가까운 근사치를 답으로 얻을 수 있다.
        for(int i=0; i<5000; ++i){
            mid = (l+h) / 2;

            // 각 변에 대한 나누기, 곱하기를 통해서 총 개수를 구할 수 있다.
            // 원하는 갯수보다 적으면 mid 값을 줄여서 들어갈 수 있는 박스를 늘리는 방식으로 가야 한다.
            if((long)(L/mid) * (long)(W/mid) * (long)(H/mid) < N){
                h = mid;
            }
            else{
                l = mid;
            }
        }

        System.out.print(l);
    }
}