[백준] 1166 선물 - 파라매트릭 서치(Paramatric Search) JAVA

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

코드설명

파라매트릭 서치(Paramatric Search)를 활용합니다.

 

문제를 풀어가면서 여러 조건들을 잘 적용해야했습니다.

1. 먼저 처음에 놓쳤었던 부분은, left + 0.000000001 부분입니다.

처음에는 left + 1 로 처리했었는데요, 생각해보면 A의 값의 절대/상대 오차는 10^-9 이기에 그 숫자만큼의 차이로 연산해야합니다.

    	while(left + 0.000000001 < right) {
...
...
...

 

두번쨰는, 연산과정에서 OverFlow 가능성입니다. 처음에 int 형을 사용하여 3개의 곱이 곱해지면서 최악의 경우 오버플로우가 발생했습니다. long 형으로 Casting하여 사용합니다. ( 피연산자 중 하나라도 long 형이면 자동으로 결과값이 long형으로 캐스팅되지만, 모두 캐스팅처리합니다.)

    private static boolean isPossible(double A) {
    	//(long)형을 사용해야 연산과정에서 OverFlow가 발생하지 않는다.
    	long count = (long) (arr[0] / A) * (long) (arr[1] / A) * (long) (arr[2] / A);
    	if(count >= N) return true;
    	else return false;
    }

 

세번째는, 시간초과입니다. 

부동소수점 특성상 경우에 따라 left + 1e-9 가 항상 right보다 작을 수 있습니다. 

이 의미는 mid가 연산되면서 1e-9 보다 작은 1e-10 레벨에서부터 mid값이 갱신됨을 의미합니다.

그래서 우리는 문제에서 절대/상대 오차를 10^-9 까지 허용하기에 iterations = 100 을 두어서 처리합니다.

iterations=100을 두면 사실상 2^100개까지 탐색할 수 있기에 충분히 탐색할 수 있습니다.

int iterations = 100;
 
while(iterations-- > 0 && left + 0.000000001< right) {
...
...
...

 

네번쨰는, left의 시작범위는 left = lo ( 0 )이다.

일반적으로 lo 는 가능한 최소값을 나타냅니다. 생각해보면 박스의 크기가 음수가 되는 경우를 의미하는데, 이는 이후에 답을 연산할떄 A의 길이가 음수로 표현되는 오류가 나타납니다.

10 1 1 1

을 처리하면 아래와 같이 비교하면 됩니다.

10 1 1 1
 
left = -1 로 처리할시
-0.9999999993
 
left = 0 처리할시
0.3333333340

left가 -1 로 처리되면서, mid값이 -0.xxx로 처리될 수 있다는 것을 유의하여 left = lo 로 수정합니다.

코드

정답코드입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	private static int C, N, M, W, H, K, A, L;
	private static int[] arr;
    private static int answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        arr = new int[3];
        L = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        arr[0] = L; arr[1] = W; arr[2] = H;
        Arrays.sort(arr);
        
        //가장 작은 숫자가 시작점입니다.
        double answer = paramatricSearch(0, arr[0]);
        System.out.println(String.format("%.10f", answer));
    }
     
    private static double paramatricSearch(double lo, double hi) {
    	double left = lo;
    	double right = hi + 1;
    	int iterations = 100;
    	
    	while(iterations-- > 0 && left + 0.000000001< right) {
    		double mid = (left + right) / 2;
    		if(isPossible(mid) == true) {
    			left = mid;
    		}else {
    			right = mid;
    		}
    	}
    	return right;
    }
    
    private static boolean isPossible(double A) {
    	//(long)형을 사용해야 연산과정에서 OverFlow가 발생하지 않는다.
    	long count = (long) (arr[0] / A) * (long) (arr[1] / A) * (long) (arr[2] / A);
    	if(count >= N) return true;
    	else return false;
    }
    
}