[백준, BOJ 2022] 사다리 (java)

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

메모리: 14,576 KB , 시간: 112 ms

사용 알고리즘: 이분 탐색, 수학, 피타고라스 정리

728x90

---

수학 공식이 적용되는 것 같은데, 적절한 공식이 떠오르지 않아 블로그를 참고했다.

 

공식을 대입하여, 이분 탐색으로 두 건물 사이의 거리를 오차 범위 이내에 오도록 하는 값을 찾으면 된다.

이분 탐색 시작 시에 값의 범위는 0 ~ Math.min(x, y)인데, 두 건물 사이의 거리가 사다리의 길이보다 길 수는 없기 때문이다.

res가 c보다 높은 곳에 위치한다면, 가운데 값을 크게 해야 더 낮은 res를 구할 수 있기 때문에 이분 탐색의 왼쪽 값을 변경해 주고

res가 c보다 낮은 곳에 위치한다면, 가운데 값을 낮게 해야 더 높은 res를 구할 수 있기 때문에 이분 탐색의 오른쪽 값을 변경해 준다.

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

public class Main {

    public static void main(String[] args) throws Exception{

        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 s = 0, e = Math.min(x, y), m;
        double h1, h2, res;
        while(e - s >= 0.001) {
            m = (s + e) / 2;

            h1 = Math.sqrt(Math.pow(x, 2) - Math.pow(m, 2));
            h2 = Math.sqrt(Math.pow(y, 2) - Math.pow(m, 2));
            res = (h1 * h2) / (h1 + h2);

            // res가 높게 나왔다면 가로폭을 더 크게 해주어야 res가 작아짐
            if(res >= c) s = m;
            // res가 낮게 나왔다면 가로폭을 더 작게 해주어야 res가 커짐
            else e = m;
        }

        System.out.println(String.format("%.3f", e));
    }
}