[Python] 2022번 사다리

2022번: 사다리 (acmicpc.net)

2022번: 사다리

---

 

22/09/02

 

 

은근히 어려웠던 문제이다. 요즘 태그를 보지 않고 문제를 푸는데, 이분 탐색을 활용하는 문제가 아니라 온전히 답안이 나오는 문제인 줄 알고 식 정리에만 시간을 온전히 쏟았다.

 

알고 보니 명확한 식으로 나오지 않는 문제임을 알고서 이분 탐색을 활용하여 문제를 풀었다.

 

식 정리가 제일 어려운 문제이다.

---

 

문제 접근 방식:

 

그냥 식 정리를 한 뒤에 이분 탐색으로 문제를 풀면 된다.

 

이 식 정리가 좀 어렵긴 하지만, 사진으로 나와있으니 참고하면 될 것이다.

 

c값

 

c값을 다음과 같이 표시를 하고, 이분 탐색으로 d값을 찾아내면서 c값과의 오차가 10^(-3) 보다 더 작아지는 순간 종료한다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 2022번 사다리
# 수학, 기하학, 이분탐색
from math import *
x, y, c = map(float, input().split())

def binary_search(low, high, x, y, c):
    mid = (low + high) / 2
    val = (sqrt(x*x-mid*mid)*sqrt(y*y-mid*mid))/(sqrt(x*x-mid*mid) + sqrt(y*y-mid*mid))
    if abs(val-c) < 0.0001:
        return mid
    if val >= c:
        return binary_search(mid, high, x, y, c)
    else:
        return binary_search(low, mid, x, y, c)

print(binary_search(0, min(x,y), x, y, c))