백준8986 전봇대

작성일 | In

문제 링크

  • http://icpc.me/8986

문제 출처

  • 2013 전국 본선 고등3

사용 알고리즘

  • Parametric Search
  • 삼분 탐색

시간복잡도

  • O(n log 1e9)

풀이

고등부 3번이라는 것이 믿기지 않을 정도로 너무 쉬운 문제입니다. 중등부 2번 정도가 적당한 것 같습니다.

전봇대들의 간격이 k일 때 이동 거리가 최소가 된다고 가정합시다.
f(x) = 간격이 x일 때 이동거리 라고 정의를 한다면, 함수 f는 k 이전에서는 순감소 함수 형태이고 k 이후로는 순증가 함수 형태입니다.

한쪽은 순감소, 반대쪽은 순증가라면 삼분 탐색을 사용할 수 있습니다.
삼분 탐색을 이용해 정답을 구해줍시다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

vector<ll> v;

ll calc(ll k){
	ll ret = 0;
	for(int i=0; i<v.size(); i++){
		ret += abs(i*k - v[i]);
	}
	return ret;
}

int main(){
	int n; cin >> n;
	v.resize(n);
	for(int i=0; i<n; i++){
		cin >> v[i];
	}

	ll s = 1, e = 1e9;
	while(s+3 <= e){
		int l = (2*s + e) / 3;
		int r = (s + 2*e) / 3;
		ll costL = calc(l);
		ll costR = calc(r);
		if(costL < costR){
			e = r;
		}else{
			s = l;
		}
	}

	ll ans = 1e18;
	for(int i=s; i<=e; i++){
		ans = min(ans, calc(i));
	}
	cout << ans;
}