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.3333333340left가 -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;
}
}