🧩 문제 : 2022 사다리
👩🏻💻 문제 정리
x, y, c가 주어졌을 때 ?를 구하면 되는 문제 !
x : 왼쪽 빌딩 위 - 오른쪽 빌딩 아래에 놓인 사다리의 길이
y : 왼쪽 빌딩 아래 - 오른쪽 빌딩 위에 놓인 사다리의 길이
c : 두 사다리가 교차하는 지점
? : 두 빌딩 사이의 거리
💪🏻 풀이 과정
1️⃣ w와 c의 관계를 나타내는 식 구하기
다음과 같이 x, y, c, w에 대하여 c에 대한 식을 유도해냈다.
# c를 구하는 함수
def f(w):
h1 = (x ** 2 - w ** 2) ** 0.5
h2 = (y ** 2 - w ** 2) ** 0.5
c = (h1 * h2) / (h1 + h2)
return c
해당 식을 만족하는 w 값을 탐색하면 된다.
❓ w값 탐색 범위는?
1. x > w, y > w를 모두 만족해야한다. -> (x^2 - 2^2)값이 음수가 나오게 되면 h1, h2는 복소수가 됨
따라서 0에서부터 x, y 중 더 작은 값까지 탐색해야한다 !
start, end = 0, min(x,y)
2️⃣ w와 c의 관계
w가 작아질수록 c 값이 커지고 있다. -> 반비례 관계
이 부분을 고려하여 이분탐색 조건을 설정해준다.
(나는 처음에 이 부분을 고려하지 않고 풀어서 틀렸었다.)
if find_c >= c:
start = mid
elif find_c < c:
end = mid
💻 정답 코드
import sys
# 입력
x, y, c = map(float, sys.stdin.readline().split())
# c를 구하는 함수
def f(w):
h1 = (x ** 2 - w ** 2) ** 0.5
h2 = (y ** 2 - w ** 2) ** 0.5
return (h1 * h2) / (h1 + h2)
# w값 탐색 범위
start, end = 0, min(x,y)
while start <= end:
mid = (start + end) / 2.0
find_c = f(mid) # c 계산
if find_c >= c:
start = mid
# 값 c의 오차 범위가 10^−3보다 작아질때까지 이분 탐색
if abs(find_c - c) < 0.0001:
break
else:
end = mid
print('%.3f'%start)
💭결과
'알고리즘' 카테고리의 다른 글
[프로그래머스 / Python] 순위 (0) | 2023.02.14 |
---|---|
[BOJ / Python] 15486 퇴사 2 (0) | 2023.02.13 |
[BOJ / Python] 3107 IPv6 (0) | 2023.02.08 |
[BOJ / Python] 25603 짱해커 이동식 (0) | 2023.02.07 |
[프로그래머스 / Python] K번째 수 (0) | 2023.02.06 |