(C++) - 백준(BOJ) 2022번 : 사다리 답

www.acmicpc.net/problem/2022

2022번: 사다리

피타고라스 정리, 그래프 식세우기를 이용해 이분탐색을 하는 문제였습니다.

풀이방법

 입력받는 x,y를 각각 a,b라고 가정한 뒤 구하려는 값을 k, 두 빌딩의 높이를 각각 A,B라고 가정했습니다. 이 때 가장 왼쪽 하단 꼭지점을 0,0으로 하여 직선 a,b에 대한 방정식을 구했습니다. 이 정보들을 공식으로 표현하면 다음과 같습니다.

 

 $A = \sqrt{a^2 - k^2}$

 $B = \sqrt{b^2 - k^2}$

 

 직선 a에 대한 방정식 f(x)

 $f(x) = -\frac{A}{k}x + A$

 

 직선 b에 대한 방정식 g(x)

 $g(x) = -\frac{B}{k}x$

 

 직선 a,b가 교차하는 점을 (c0,c)하고 가정했을 때 다음과 같은 공식이 성립합니다.

 $f(c0) = g(c0) = c$

 

 $g(c0) = \frac{B}{k}c0$ 이므로 

 $c0 = \frac{k}{B}c$ 가 됩니다.

 

 $f(c0)$의 c0에 상기 식을 대입하면 

 $ f(c0) = -(A \times (k\times{c} \div{B}) \div {k}) + A $ 가 됩니다.

 

f(c0)의 값이 > c라면 간격을 줄여줘야되므로 l = k;

반대라면 r = k;입니다.

 

최종 답은 c이하인 l을 출력하면 됩니다.

 

* loop문 작성시 유의하셔야 될 부분

while(r - l > 1e - 9) => r-l이 1e-9보다 항상 클 경우가 있으므로 for문으로 loop횟수를 정해서 답을 구하셔야 시간초과가 발생하지 않습니다.

Code

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

double f(double x,double k,double A){
    return - (A * x / k) + A;
}

int main(){
    double a,b,c;
    cin >> a >> b >> c;
    double l = 0;
    double r = min(a,b);
    for(int i = 0; i < 1000; i++){
        double k = (r+l)/2.0;
        double A = sqrt(a*a - k*k);
        double B = sqrt(b*b - k*k);
        double c0 = k * c / B;
        
        if(f(c0,k,A) > c){
            l = k;
        }else r = k;
    }
    printf("%.3lf",l);
}