[SWEA] 1245. [S/W 문제해결 응용] 2일차 - 균형점 - Binary Search

이 글은 SW Expert Academy에 있는 문제를 풀고 정리한 글입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15MeBKAOgCFAYD&categoryId=AV15MeBKAOgCFAYD&categoryType=CODE&&&

우선, 가능한 균형점의 위치가 정수가 아닌 실수이기 때문에, 가능한 범위를 모두 탐색해보는건 불가능합니다.

무한히 많은 후보가 존재하기 때문이죠.

이 문제를 읽으면서 제가 괜히 궁금해 졌던건

n-1개의 균형점이 꼭 자성체들 사이의 n-1개의 구간들에 하나씩만 배치 되는가,

즉 두개의 자성체 사이에 두 개 이상의 균형점이 존재할 수 있는가

였습니다.

문제를 읽다보면 자연스럽게 그럴거라고 추측하고 넘어갈 법하지만

깔끔하게 확신을 하고 넘어가고 싶었습니다.

어느 한 점에 작용하는 중력이 왼쪽으로 작용하면 음수, 오른쪽으로 작용하면 양수라고 정의하면,

중력 계산식에서 거리 값 d의 제곱이 분모에 있기 때문에,

점이 물체에 무한히 가까워질 수록 중력의 크기는 그 가까워지는 자성체의 방향으로 무한히 세지는 것을 알 수 있습니다.

중력의 크기는 거리값이 연속적으로 변함에 따라 연속적으로 변하게 되고

한 구간 안에서 x축을 따라 이동할 수록 기울기의 부호는 달라지지 않을 것입니다.

즉, 오른쪽으로 이동한다면 오른쪽 방향으로 중력이 강해지지, 강해졌다가 약해졌다가 하지는 않을 것입니다.

(이동함에 따라 중력의 값이 바뀌는 요소가 d뿐이기 때문입니다.)

따라서, 각 자성체 주변에서 극한의 값을 갖게 된다면

그 구간에서는 0의 값을 가지는 곳이 한 곳일 수 밖에 없습니다.

이를 그래프로 표현하면

이렇게 되는 것을 알 수 있습니다

그렇다면,

만약 두 자성체의 사이에서 왼쪽 자성체의 위치를 left, 오른쪽 자성체의 위치를 right로 정의하고,

f(x)를 위치가 x인곳에서 작용하는 중력의 크기로 정의한다면

f(left)<0<=f(right)가 성립함을 알 수 있습니다.

mid=(left+right)/2로 정의하고 f(mid)의 부호를 확인하면서 left, right의 값을 바꿔간다면

f(x)=0인 x에 접근할 수 있을 것입니다.

이분법을 적용해서 x를 찾는 함수입니다.

제 코드입니다 ㅎㅎ 감사합니다.

http://colorscripter.com/s/7OJakRU