[BOJ 8986 // C++] 전봇대

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 8986번 문제인 전봇대이다.
문제는 아래 링크를 확인하자.

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

8986번: 전봇대

전봇대의 개수를 N이라 하자.

함수 f(x)를 각 인접한 전봇대 사이 간격을 x로 만들 때의 전봇대 이동 거리로 정의하자.

이것은 |xi-x*i| (0<i<N)들의 합과 같다.

각 |xi-x*i|는 아래로 볼록한 그래프이고, 아래로 볼록한 함수의 합은 다시 아래로 볼록한 함수가 되므로, 주어진 함수는 아래로 볼록한 함수이다.

 

따라서, 다음과 같은 방식으로 x값을 이분탐색(binary search)을 하면 f(x)가 최소가 되게 하는 x값을 구할 수 있다:

이분탐색을 하는 구간 [L,R]의 새로운 mid값에 대하여, f(mid) <= f(mid+1)라면 찾는 x값은 [L,mid]에서 꼭 찾을 수 있고, 그렇지 않다면 [mid+1,R] 구간에서 꼭 찾을 수 있다.

 

또는 삼분탐색(ternary search)을 해도 문제를 해결할 수 있을 것이다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll N;
ll arr[100000];

ll func(ll x) {
	ll ret = 0;
	for (ll i = 1; i < N; i++) {
		ret += abs(arr[i] - i * x);
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];

	ll L = 0, R = 1000000000;
	while (L < R) {
		ll mid = (L + R) / 2;
		ll midval = func(mid);
		ll rightval = func(mid + 1);
		if (midval <= rightval) R = mid;
		else L = mid + 1;
	}

	cout << func(L);
}