백준 8986. 전봇대

기본적인 삼분탐색 문제, 처음엔 단순 이분법 parametric search로 푸는 문제인줄 알고 한참을 고민했다. 

삼분탐색으로 풀 생각을 하고 삼분탐색에 대해 살짝 맛을 봤더니 삼분탐색도 이분탐색으로 하는 방법이 있길래 풀어보았다.

삼분탐색에 대한 정리는 https://mingnine9999.tistory.com/34에 해두었다.

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

8986번: 전봇대

전봇대들을 모두 같은 거리만큼 떨어져 있도록 옮겨야 하는데, 가장 최소로 움직이는 거리를 찾아야 하는 문제이다.

전봇대가 모두 같은 거리만큼 떨어져 있어야 하므로 두 전봇대사이의 거리를 x, 그 거리로 모두 이동하는데 움직이는 거리를 y로 하는

함수의 최솟값을 찾는 문제로 생각하면 쉽다. f(x) < f(x + 1) 인 최소의 x를 찾으면 되는데, 이 값을 이분탐색으로 찾아주기만 하면 

풀리는 문제..!! 덕분에 삼분탐색에 대해서도 고민하고 괜찮은 문제인 것 같다.

https://github.com/MingNine9999/algorithm/blob/master/Problems/boj8986.cpp

MingNine9999/algorithm