[python] 백준 2022 사다리

https://www.acmicpc.net/problem/2022

2022번: 사다리

 

문제 해결

다음과 같이 $h_{1}$, $h_{2}$, $w$, $w_{1}$, $w_{2}$를 정의하자.

$w_{1} : c = w: h_{2}$와 $w_{2}:c = w: h_{1}$임을 이용해서 c의 값을 $h_{1}$과 $h_{2}$의 값으로 나타낼 수 있다.

$ w = w_{1} + w_{2} = \frac{cw}{h_{2}} + \frac{cw}{h_{1}} = cw \frac {h_{1}+h_{2}} {h_{1}h_{2}}$

$c = \frac{h_{1}h_{2}} {h_{1}+h_{2}}$

우리는 정확한 $w$ 값을 모르기 때문에 $h_{1}$과 $h_{2}$도 모른다.

하지만 0≤$w$ ≤ $min(x,y)$이기 때문에 이진분류를 통해서 w의 근삿값을 맞추어가며 피타고라스 정리로 $h_{1}$, $h_{2}$의 값을 구한다음 c를 공식을 통해 구한다음 주어진 c와 맞는지 확인하면서 만약 주어진 $c$값보다 크다면 $w$값을 늘려야한다는 것이므로 최소범위를 $w$로 조정하며 다시 계산하고 주어진 $c$값보다 작다면 $w$값을 줄여야한다는 것이므로 최대범위를 $w$로 조정하며 다시 계산을 해나가며 조절한다. 반복적으로 행하며 $w$의 값을 추론하도록 알고리즘을 짜야한다.

 

CODE

import sys
input = sys.stdin.readline

def get_c(x,y,w):
    h1 = (x**2-w**2)**0.5
    h2 = (y**2-w**2)**0.5
    c = h1*h2/(h1+h2)
    return c

if __name__=='__main__':
    x, y, c = map(float, input().split()) # x, y, c의 값 
    s, e = 0, min(x,y) # w의 가능한 범위 s이상 e이하
    res = 0
    while e-s > 0.000001:
        m = (s+e)/2
        res = m
        if get_c(x,y,m) >= c:
            s = m
        else:
            e = m
    print(res)