[백준][C++] 8986번: 전봇대 <112>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 생각의 흐름 이번 문제는 3분탐색을 이용하면 해결할 수 있다. 우선 문제가 3분탐색으로 해결 가능한지를 확인하기 위해서는 함수의 형태를 확인해야 할 것 이다. f(x) : 전봇대 사이의 거리를 x로 지정할때, 총 옮겨야 하는 거리의 합 초기 전봇대의 좌표를 d0, d1, d2, ..., d(n - 1)이라고 하자. 이웃된 전봇대의 거리를 일정하게 x로 맞춘다고 가정하면, 이때의 좌표는 0, 1 * x, 2 * x, ..., (n - 1) * x로 표현이 가능하다. 따라서 이동거리함수 f(x)는 다음과 같이 표현가능하다. f(x) = | x - d0 | + | 2 * x - d1 | + ... + | (n - 1) * x..........

원문링크 : [백준][C++] 8986번: 전봇대 <112>