백준 2022 사다리 [java]

22 Jun 2022 in Develop / Solving

java

문제 분석

• 두 건물 사이에 길이가 x, y인 사다리를 놓는다.
• 한 사다리는 왼쪽 건물을 받치게 놓고, 한 사다리는 오른쪽을 받치게 놓아서 두 사다리는 교차한다.
• 사다리는 높이 c에서 교차한다.
• 이 때, 두 건물은 얼마나 떨어져 있는가.

입력조건

사다리 길이 x y 교차점의 높이 c

풀이과정

• 이게 왜 이분탐색으로 분류되어 있지?
  라는 생각으로 식을 정리해봤는데, 이분탐색이 맞았다.

• 문제가 10^-3 까지의 오차를 허용한다는게 꽤 큰 포인트이다.
• 꽤 큰 오차를 하용한다는 것으로, 계산 방식에 따라 편차지가 나올 것이라는 것.
  아래 사진의 식을 보면 루트 식들을 어떻게 전개한 상태에서 계산하냐에 따라 편차치가 생길 수 있다는 것을 알 수 있다.

• 위 사진은 구할 길이를 t로 두고 t를 구할 수 있는 식을 찾아낸 것이다.
• 0을 하한, x y 중 작은 값을 상한으로 두고, t를 구하는 이분탐색을 돌린다.
• 위 식으로 c를 구해서 c-0.0001 < 계산한 c < c+0.0001 일 때 정답으로 출력하고(10^-3까지 정답으로 인정하므로), 나머지 경우에 반복한다.

추가

소수 써서 오차 허용하는 문제는 대부분 정답률이 개판이던데, 얘는 테스트케이스가 조금 순탄한 것 같다.

전체 코드

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

public class BJ2022_사다리 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        double x = Double.parseDouble(st.nextToken());
        double y = Double.parseDouble(st.nextToken());
        double c = Double.parseDouble(st.nextToken());

        double left = 0;
        double right = Math.min(x, y);
        
        while( left < right ) {
            double t = (right + left) / 2;
            double mid = (Math.sqrt(x*x - t*t) * Math.sqrt(y*y - t*t)) / 
                         (Math.sqrt(x*x - t*t) + Math.sqrt(y*y - t*t));
            // System.out.println(t + " " + mid);

            if(mid < c - 0.0001D) right = t - 0.0001D;
            else if (mid > c + 0.0001D) left = t + 0.0001D;
            else {
                System.out.printf("%.3f", t);
                return;
            }
        }
        System.out.printf("%.3f",right);
    }
}