[BOJ 2022] 사다리

(2022년의 마무리를 맞아서) 2022번 사다리라는 문제를 풀었습니다.

 

난이도는 솔브드 기준 골드 5고, 실제로(제 기준)그리 어려운 문제는 아니지만 적당히 접근하는 방법과 풀이가 problem solving과 단순 기하학/수학이 잘 접목되어서 이루어지는 느낌이라 꽤 괜찮은 수학 문제라고 생각했습니다.

 

문제 링크는 다음과 같습니다.

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

2022번: 사다리

 

문제에 나오는 이미지

문제 자체는 아주 간단합니다. 위 그림에서 x, y, c가 주어졌을 때 두 건물 사이의 거리를 구하라는 문제예요.(조금 약화시킨다면)중학교 3학년 수학 응용 문제 정도로 나와도 괜찮을 정도라고 생각합니다.

 

중학생이 된 기분을 느끼면서, 직각 삼각형의 닮음과 피타고라스의 정리를 이용해서 적당히 그림을 정리해봅시다.

여기서 빨간색으로 그려진 두 직각삼각형은 닮음입니다.

우선 구하고자 하는 거리를 a라고 둔다면, 위와 같이 피타고라스의 정리를 통해서 왼쪽/오른쪽 긴 세로선의 길이를 구할 수 있습니다. 그리고 왼쪽 삼각형, 오른쪽 삼각형 각각에 대해 닮음비를 적용하면 다음과 같이 수식을 적용할 수 있습니다.

 

$$ \frac{\sqrt{x^2-a^2}}{a}  = \frac{c}{k} $$

$$ \frac{\sqrt{y^2-a^2}}{a} = \frac{c}{a-k} $$

$$ \frac{a}{\sqrt{x^2-a^2}} + \frac{a}{\sqrt{y^2-a^2}} = \frac{a}{c} $$

$$ \frac{1}{\sqrt{x^2-a^2}} + \frac{1}{\sqrt{y^2-a^2}} = \frac{1}{c} $$

 

에? 이건 a를 알면 c를 구할 수 있는 식 같은데, 대체 이걸로 뭘 할 수 있을까요?

 

물론 수학적으로 이 방정식을 예쁘게 푸는 것은 결코 쉬운 일이 아닙니다. 울프람 알파 선생님께 한번 물어봤더니

이 뒤로도 식이 쭈우우우우욱 있습니다.

네. 아마도 제곱 두번 하면서 예쁘게 정리하면 4차 방정식이 나오고, 우리의 울프람신님께서는 친히 그걸 4차방정식의 근의 공식에 넣었습니다. 물론 4차라서 근의 공식이라도 나오는 게 다행이긴 한데, 일반적으로 정리되는 예쁜 해는 없을까요? 정말로 저희는 망한걸까요? 이정도 구현량이면 솔직히 골드 5가 아니라 다이아는 받아야 하지 않을까요?

 

물론 저 식을 직접 넣는 것이 정해는 아닙니다! 우리가 주목할 만한 성질은, a가 커지면 커질수록

의 값도 커진다는 점입니다. a가 커지면 저 식 안에 있는 분모가 작아지고, 분모가 작아지는 게 결국 숫자는 커지게 하니까요. 이런 성질을 가진 걸 잘 이용하는 알고리즘으로는 다름아닌 이분 탐색이 있습니다! a는 min(x, y)를 넘어갈 수는 없으니까, 최대 bound를 그정도로 잡아두고, 문제에서 허용한 오차인 10^-3 정도 안으로 좁혀지면 그 값을 출력하는 식으로 해결할 수 있습니다.

 

풀이 코드는 다음과 같습니다.

 

a,b,c=map(float,input().split())
def f(x):
	return 1/(b**2-x**2)**0.5 + 1/(a**2-x**2)**0.5

lo = 0
hi = min(a,b)

while abs(hi-lo)>1e-6:
	mid = (lo+hi)/2
	if f(mid) < 1/c: lo=mid
	else:hi=mid

print((lo+hi)/2)

 

이분탐색 입문용으로도, 간단한 기하학 연습 문제로도 괜찮은 문제였다고 생각합니다. 조금 더 나아가서는 방정식을 풀기 위해서 수치해석학적인 기법들을 사용해야 하는 문제들이 BOJ에 종종 있는데, 이런 응용 문제들에서도 사실 웬만큼 복잡한 수치해석학 테크닉이 필요하지는 않고, 결국 테일러 급수+이분탐색 정도로 귀결되는 경우가 많이 있습니다. 이러한 문제들의 입문 격이라고 생각하면 되겠네요.

 

혹시 질문이나 잘못된 점 있으면 댓글로 달아주세요! 감사합니다.

 

여담으로 수식 입력 기능을 새로 넣어봤는데, 적용이 어디는 됐다가 어디는 안됐다가 하는 것 때문에 무지하게 곤혹을 치뤘네요. 아예 이럴 걱정 없는 깃허브 블로그로 이사가야 하나...