[백준/알고리즘] 8986번 전봇대 (플래티넘 5)

클릭하면 백준 페이지로 이동합니다.

---

 

BOJ 8986번

 

현재 전봇대의 위치가 X축 위에 좌표로 나타내져 있다. (첫번째 전봇대는 항상 0에 위치한다.)
이 전봇대들을 일부 움직여서, 서로 이웃한 전봇대 사이의 거리를 일정하도록 옮기려고 한다.
이때, 이웃한 전봇대 사이의 거리를 일정하도록 하는 이동거리의 합의 최솟값을 출력하시오.

 

풀이 알고리즘 : 이분탐색, 삼분탐색

 

지금 풀고있는 백준 문제집의 마지막 문제여서 처음보는 삼분탐색 알고리즘도 공부하고, 겨우겨우 풀게 되었다.

 

초기 전봇대의 좌표를 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 - d(n - 1) |

 

이를 그래프로 간단하게 표현하면,

 

이동거리함수 f(x)

와 같이 x가 0부터 최솟값이 되는 거리까지 이동거리가 감소하다가, 그 이후부터는 쭉 올라가는 모양을 가진다.

 

이분탐색과 같이 lo값과 hi값을 가지고, p1과 p2 두 점을 정하여 최솟값을 확인한다.

 

두가지 케이스가 있다.

 

첫번째는 왼쪽 값인 p1이, p2보다 작거나 같은 경우이다.

 

p1 <= p2인 경우

이 경우, p2보다 p1이 작으므로, 최솟값은 p2일때의 거리보다 작은 값 중에 있다는 것을 의미한다.

 

즉, hi값을 p2일때의 거리로 변경하여 탐색 범위를 줄여나간다.

 

두번째는 왼쪽 값인 p1이, p2보다 큰 경우이다.

 

p1 > p2인 경우

이 경우, p2가 p1보다 작으므로, 최솟값은 p1일때의 거리보다 큰 값 중에 있다는 것을 의미한다.

 

즉, lo값을 p1일때의 거리로 변경하여 탐색 범위를 줄여나간다.

 

이후 반복문을 빠져나갔을때, lo값 또는 hi값 중 하나가 정답인 최솟값이 된다.

 

주의해야 할 점은, 이동거리함수 f(x)를 계산하는 함수를 선언했는데, 값이 10^10정도의 매우 큰 값이 들어가면, 계산 도중 long long 범위를 초과하므로, 삼분탐색 범위를 잘 맞춰주어야 한다.

 

처음 써보는 알고리즘이고, 플래티넘 문제여서 어렵게 풀었다. hellogaon의 블로그에서 참고랑 조언을 많이 받았습니다.

 

 

소스코드 보기

 

#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))

// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};

// 전역변수
ll n;
vector<ll> arr;

// f(d) : 일정한 거리가 d일때, 전봇대를 이동하는 횟수
ll f(ll d) {
	ll cnt = 0;
	for(ll i = 0; i < n; i++) {
		cnt += abs(arr[i] - i * d);
	}
	return cnt;
}

int main(void) {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;
	for(int i = 0; i < n; i++) {
		ll temp; cin >> temp; arr.push_back(temp);
	}
	if(n == 1) {
		cout << "0";
		return 0;
	}

	// 삼분탐색
	ll le = 0, ri = (ll)(1e9 + 1);
	while(le + 2 < ri) {
		ll fst = (2 * le + ri) / 3, scd = (le + ri * 2) / 3;
		ll lo = f(fst), hi = f(scd);

		if(lo <= hi) {
			// lo와 hi 사이에 최솟값 있음
			ri = scd;
		} else {
			le = fst;
		}
	}

	ll ans = 100000000000000;
	
	for(ll i = le; i <= ri; i++) {
		ans = min(f(i), ans);
	}

	cout << ans << "\n";

	return 0;
}