백준 문제풀이 : (2022) 사다리 - c/c++

문제 주소 : https://www.acmicpc.net/problem/2022

2022번: 사다리

 

시간 제한	메모리 제한	난이도	알고리즘 분류
2초	128 MB	Gold 4	수학 / 기하학 / 이분 탐색

 

 

문제

---

 

 

풀이

---

 

?를 w로 두고, 입력받는 변수 x, y, c를 활용해 다음과 같이 식을 정리할 수 있다.

 

 

위 과정을 통해 알아낸 최종식을 풀어 w를 알아내야 하지만, 루트와 제곱이 난무하는 복잡한 식이기 때문에 순수 계산으로는 답 계산이 어렵다.

 

따라서 w가 될 수 있는 최솟값과 최대값을 구하여 이분탐색을 통해 위 식에 들어맞는 w값을 찾아나가야 한다.

 

w의 최솟값은 사다리를 걸쳐놓은 두 건물이 완전히 맞붙었을 때이므로, min = 0 이다.

w의 최대값은 두 건물이 점점 멀어지다가 두 사다리 중 더 작은 쪽이 완전히 바닥에 누워 c가 0이 되었을 때다.

따라서 max= (x>y) ? y : x 이다.

 

주의할 점은, 문제에서 정해놓은 실수 오차 범위가 10의 -3승까지라는 것이다. 

w의 값을 추측해나가며 c와 w의 차이가 오차 범위 내로 줄어들면 반복을 중지하고 값을 출력한다.

 

식 중  x, y, w은 제곱을 해야하는 단계가 있으므로 변수는 안전하게 double 형을 사용한다.

 

 

코드 작성

---

#include <iostream>
#include <math.h>
#define EPS 0.000001

using namespace std;

int findResult(double w, double x, double y, double c) {
    double num = (sqrt(y*y-w*w)*sqrt(x*x-w*w))/(sqrt(y*y-w*w)+sqrt(x*x-w*w));
    
    if (fabs(c-num)<EPS) return 0; //범위값이면 0 리턴
    else if (c<num) return 1; //c가 더 작으면 1 리턴 
    else return 2;  //c가 더 크면 2 리턴
}

int main() {
    double x, y, c;
    scanf("%lf %lf %lf", &x, &y, &c);
    
    double min = 0;
    double max = (x>y) ? y : x;
    double result=0;
    
    while (true) {
        double half=(min+max)/2;
        int check = findResult(half, x, y, c);
        if (check==0) { // 오차 범위 내의 값을 찾았으면 result값 저장하고 반복 종료.
            result=half;
            break;
        } else if (check==1) min=half;
        else max=half;
    }
    
    printf("%f", result);
}

 

 

END.