[백준 BOJ] 2022 사다리 (python)

문제 링크 : https://www.acmicpc.net/problem/2022

2022번: 사다리

요즘 계속 기하학 문제를 푸니 카테고리를 따뤄 나눴습니다.

그리디 문제도 번갈아가며 자주 푸는데, 아직 마땅히 풀이할 문제가 없지만 일단 그리디 카테고리도 추가하였습니다.

 

사실 이번 문제 기하학의 탈을 쓴 이분탐색 문제입니다.

어떻게보면 계산하기 어려운 기하문제를 코드에서는 이렇게 풀 수 있다는 것을 알려주는 문제 같습니다.

 

이분탐색

이진탐색이라고도 하는 Binary Search는 정말 자주 쓰는 탐색법입니다.

시간복잡도를 로그로 줄여주는 고마운 친구이기 때문이죠.

정렬된 상태에서 사용 가능하고 일반적으로 시작과 끝에 대한 변수를 두고 둘의 중간값을 확인하고 업데이트하는 과정을 반복하는 것으로 구현됩니다.

이 문제는 실수에 대해 이분탐색을 하므로 종료 조건이 없다면 무한하게 탐색을 하게 되므로 문제 조건인 허용 오차까지만 탐색을 해주어야 합니다.

 

이분탐색을 통해 너비를 유추하고 두 사다리의 총 높이를 계산한 후 그에 대한 주어진 높이 c에 대한 비율을 계산해 주었습니다.

만약 두 비율의 합이 1이라면 높이 c가 두 사다리 교점이 된다는 의미이고 그때 유추된 너비를 본 문제의 답이라고 할 수 있습니다.

 

x, y, c = map(float, input().split())
s = 0
e = (min(x, y) ** 2 - c ** 2) ** 0.5
while True:
    m = (s + e) / 2
    x_h = (x ** 2 - m ** 2) ** 0.5
    y_h = (y ** 2 - m ** 2) ** 0.5
    t = c / x_h + c / y_h
    if 0.9999 < t < 1.0001:
        print(m)
        break
    if t < 1:
        s = m
    else:
        e = m