2022번 사다리

문제 설명

이번 문제는 길이가 x, y인 사다리가 있고 두 빌딩에 기대져 있을 때, 두 사다리가 땅에서부터 정확하게 c인 지점에서 서로 교차한다면 두 빌딩은 얼마나 떨어져 있는지 찾는 문제입니다.

 

문제 풀이

아이디어

x,y 식 구하기

x가 빌딩과 닿아있는 지점부터 바닥까지의 길이를 b, y가 빌딩과 닿아있는 지점부터 바닥까지의 길이를 d

빌딩이 떨어져 있는 거리를 a라고 할 때 x,y,a,b,c를 이용해 문제에서 주어진 조건으로 식을 만들어 보겠습니다.

사다리

피타고라스의 정리를 이용해

x^2 = b^2+a^2

y^2 = d^2+a^2

식을 구할 수 있습니다.

 

또한 닮음을 이용한 식을 구할 수 있습니다.

x빌딩의 바닥 부분을 0,0이라고 한다면 y사다리는 y=(d/a)x 그래프가 되므로 x빌딩으로부터 두 사다리가 맞닿는 곳까지의 거리는 ac/d입니다.

이를 이용해 닮음을 이용하면

사다리(닮음)

 

 

 

 

 

 

 

a-ac/d : c = a : b 라는 닮음 식을 만들 수 있고 이를 통해

c = bd/(b+d)라는 식을 만들 수 있습니다.

 

 

 

 

 

 

 

 

 

 

탐색

문제에서 a는 0<=a<=min(x,y) 임을 알 수 있습니다. (x,y는 소수 6자리까지 주어지며 3,000,000,000보다 작거나 같습니다.)

a를 구하려면 0부터 min(x,y)까지의 수를 탐색하면서 찾을 수 있게 되는데 단순 반복문으로 풀게 된다면 최악의 경우 3,000,000,000,000번의 탐색을 해야할 수도 있습니다. x,y는 (최대 3,000,000,000.999까지 허용되므로)

 

그러므로, 단순 탐색이 아닌 이분 탐색을 통해 좀 더 빠르게 문제를 해결 할 수 있습니다.

 

 

문제 풀이

위의 식 활용

위에서 피타고라스를 통해 얻어낸 식으로 b,d를 구해보자면

b = (x^2-a^2)^0.5

d = (y^2-a^2)^0.5

입니다.

여기서 구한 b,d를 닮을 이용한 식에 대입하면

c = ( (x^2-a^2)^0.5 * (y^2-a^2)^0.5 ) / ( (x^2-a^2)^0.5 + (y^2-a^2)^0.5 ) 임을 알 수 있습니다.

문제에서 x, y, c 값은 주어지므로 위의 식을 해결할 수 있습니다.

 

이분 탐색

위에서 구해낸 식에서 a의 값을 이분탐색으로 찾으면 됩니다.

a는 0<=a<=min(x,y)이므로 해당 범위내에서 이분탐색으로 a를 찾으면 시간 내에 a를 찾을 수 있습니다.

여기서 x,y는 소수 6자리까지 주어진다고 했으므로, 이분탐색의 범위도 소수 6자리까지 찾으면될 것 같습니다.

 

 

 

해결

이번 문제는 식을 구하긴 했지만 어떻게 해당 숫자를 찾을 수 있지에 대한 생각을 해내지 못했습니다.

현실에서는 바로바로 구하면 되는 것을 코드로 구현할 수 있는 방법을 찾지 못해 결국 알고리즘 분류를 확인한 후 풀 수 있었습니다.

 

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

2022번: 사다리

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/2022.py