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) |
이를 그래프로 간단하게 표현하면,
와 같이 x가 0부터 최솟값이 되는 거리까지 이동거리가 감소하다가, 그 이후부터는 쭉 올라가는 모양을 가진다.
이분탐색과 같이 lo값과 hi값을 가지고, p1과 p2 두 점을 정하여 최솟값을 확인한다.
두가지 케이스가 있다.
첫번째는 왼쪽 값인 p1이, p2보다 작거나 같은 경우이다.
이 경우, p2보다 p1이 작으므로, 최솟값은 p2일때의 거리보다 작은 값 중에 있다는 것을 의미한다.
즉, hi값을 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;
}
'백준_BOJ > BOJ (플래티넘)' 카테고리의 다른 글
[백준/알고리즘] 17941번 목장 CCTV (플래티넘 5) (0) | 2020.07.31 |
---|