[BaekJoon] 2022번 - 사다리 [Java][C++]

문제 링크

---

1. 문제 풀이

주어진 문제에 대해 아래와 같이 각 변에 길이에 대한 변수명을 넣어줬다.

이러면 삼각형의 닯음을 활용하여 $\dfrac{w_1}{c} = \dfrac{w_1 + w_2}{h_2}$ 와 $\dfrac{w_2}{c} = \dfrac{w_1 + w_2}{h_1}$ 식을 얻을 수 있다.

위 두 식에서 좌변과 우변을 각각 더하면 $\dfrac{w_1 + w_2}{c} = \dfrac{w_1 + w_2}{h_2} + \dfrac{w_1 + w_2}{h_1} = \dfrac{(w_1 + w_2)(h_1 + h_2)}{h_1 \cdot h_2}$ 가 되며 $(w_1 + w_2)$ 를 약분 후 $c$ 에 대해 정리하면 $c = \dfrac{h_1 \cdot h_2}{h_1 + h_2}$ 임을 알 수 있다.

$h_1$ 과 $h_2$ 는 피타고라스 정리를 활용하면 구할 수 있는데, 이때 밑변의 길이를 알아야한다. 밑변의 길이는 $0$ 보다는 커야하고 삼각형이므로 빗변보다는 짧아야한다. 상한과 하한이 있으므로 매개 변수 이분 탐색을 활용하면 되며 정수값에 대한 이분 탐색이 아니라 실수 값에 대한 이분 탐색이므로 mid를 left 또는 right로 이동시키되 오차 이내인 동안만 반복해주면 된다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

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());

        double x = Double.parseDouble(st.nextToken());
        double y = Double.parseDouble(st.nextToken());
        double c = Double.parseDouble(st.nextToken());

        System.out.println(lowerBound(x, y, c));
    }

    static double lowerBound(double x, double y, double c) {
        double left = 0;
        double right = Math.min(x, y);

        while (right - left > 1E-3) {
            double mid = (left + right) / 2;

            double h1 = Math.sqrt(x * x - mid * mid);
            double h2 = Math.sqrt(y * y - mid * mid);

            if (c < h1 * h2 / (h1 + h2)) {
                left = mid;
            } else {
                right = mid;
            }
        }

        return right;
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

double lower_bound_param(double x, double y, double c) {
    double left = 0;
    double right = min(x, y);

    while (right - left > 0.001) {
        double mid = (left + right) / 2;

        double h1 = sqrt(x * x - mid * mid);
        double h2 = sqrt(y * y - mid * mid);

        if (c < h1 * h2 / (h1 + h2)) {
            left = mid;
        } else {
            right = mid;
        }
    }

    return right;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    double x, y, c;
    cin >> x >> y >> c;
    cout << lower_bound_param(x, y, c);
}

---