[BOJ] 8986번: 전봇대

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

문제에서 요구하는 것은 결국

의 최솟값을 찾는 것입니다. 이 때 중요한 성질은, f(d) 함수가 아래로 볼록한 함수라는 것입니다. d가 증가함에 따라 값이 커지는 항도 있고 작아지는 항도 있을텐데, 분명한 것은 d가 x(i)/i 를 넘는 순간 그 항은 d가 증가함에 따라 값이 커지는 항이므로 f'(d)는 계속 증가하기 때문입니다.

이 성질에 따라 삼분탐색을 하면 됩니다.

https://github.com/blisstoner/BOJ/blob/master/8986.cpp