[백준 19943] 조명등

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

예선 당일 이 문제를 보고 기하 문제인가? 라고 생각했었다. 왜냐하면 정올에서 생각보다 킬러문제로 기하 부분을 많이내기 때문이다.

 

하지만 시간도 부족했고, 이런 문제 유형은 어떻게 사고해야되는 지 난감해서 \(2\)솔로 끝냈다.

이 문제를 너무 궁금해서 예선 끝나고 여러 커뮤니티에서 찾아보았다. ConvexHull Trick으로 푸는 것이 정해였다. 약간이나마 dp로도 풀 수 있지 않을까 생각해보았지만 포기하였다.

하지만 너무 이 문제를 풀고 싶어서 ConvexHull Trick도 공부하고 열심히 사고했다.

풀이

1. 조명등 설치 후보 찾기

첫번째로 문제에서 제시하는 조명등을 비추는 비용에 대해서 먼저 구해보자.

위와 같이 조명등을 비추는 데 비용을 알 수 있다.

다음으로 우리가 조명등을 비칠 수 있는 후보에 대해서 알아보자.

이런 좌표에서 해결하는 문제는 어떤 후보를 정해놓고 문제를 풀어야 한다. 아래의 사진을 보면 쉽게 알 수 있다.

위의 사진으로 알 수 있는 사실은 어떤 \(a\)번째 조각품 ~ \(b\)번째 조각품을 모두 커버할 수 있는 좌표는

\(a\)번째 조각품의 좌표를 지나가는 \(45°\)직선과 \(b\)번째 조각품의 좌표를 지나가는 \(-45°\)의 직선의 교점

에서 조명등을 설치한다면 최적해라고 생각해볼 수 있다.

하지만 왼쪽의 사진과 같이 반례가 생길 수 있는 데 이와 같으면 오른쪽처럼 설치하는 것이 최적해일 것이다.

더욱 생각해보자. 이 케이스에서 찾아낼 수 있는 사실은 \(1\)번 조각품을 배제해도 된다는 것이다. 왜냐하면 \(2\)번 조각품을 비치게 되면 자연히 \(1\)번도 비추게 된다.

이러한 \(1\)번 조각품 같은 케이스를 어떻게 검출할까. 아래의 이미지를 보면 된다.

$$ 45^\circ function : f(x) = x + y_i - x_i$$

$$ -45^\circ function : f(x) = -x + x_i + y_i$$

$$ corss(i,j)_x = \frac{x_i+x_j-y_i+y_j}{2} : 교점의 x 좌표 $$

왜 이게 성립되는 지는 직접 여러 케이스를 만들어서 해보자.

위의 방법을 사용하여 \(1\)번과 같은 케이스들을 모두 없애주자. 이 작업은 Stack을 사용하여 \(O(n)\)만에 처리해줄 수 있다.

그러므로 조명등 설치에 대한 후보군을 모두 도출해낼 수 있다.

2. 조명등 설치 최소 비용 찾기

최소값을 찾는 다는 것은 dp로 해결할 수 있다는 뜻이다. 그러면 지금까지 얻은 정보로 dp식을 세울 수 있다.

$$ dp[i]\;:\;i번째\;조명등까지\;설치하는\;데\;최소비용$$

$$ dp[i]\;=\;min_{0 \le j<i}(dp[j]+cross(j+1,i)^2)$$

점화식을 세울 수 있지만 시간 복잡도는 \(O(n^2)\)이다. 그래서 ConvexHull Trick으로 최적화하는 문제이며, Convexhull Trick을 적용할 수 있는 점화식으로 식을 전개하면

$$ dp[i]\;=\;min_{0 \le j < i}(-\frac{1}{2}(x_i+y_i)(x_{j+1}-y_{j+1})+dp[j]+\frac{(x_{j+1}-y_{j+1})^2}{4})+\frac{(x_i+y_i)^2}{4}$$

이런식으로 전개가 ConvexHull Trick을 적용할 수 있는 형태가 된다.

또한 \(x_j+1 - y_j+1\) 부분이 단조형태야 되는 데 처음에는 단조형태를 가지고 있지 않지만 조명등 설치 후보를 추려내게 되면 단조형태를 띈다는 것을 알 수 있다.

3. 소스코드

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
vector<ll> px, py;
vector<ll> lx, ly;
 
double cross(int a, int b) {
    return (double)(px[a] + px[b] - py[a] + py[b]) / 2.0;
}
 
//ConvexHull Trick 구조체
ll la[101001], lb[101001];
struct convex {
    int sz;
 
    void Init() {
        sz = 0;
        memset(la, 0, sizeof(la));
        memset(lb, 0, sizeof(lb));
    }
    double cross(int x, int y) { return (double)(lb[y] - lb[x]) / (la[x] - la[y]); }
    void insert(ll a, ll b) {
        la[sz] = a;
        lb[sz] = b;
 
        while (sz > 1 && cross(sz - 2, sz - 1) > cross(sz - 1, sz)) {
            la[sz - 1] = la[sz];
            lb[sz - 1] = lb[sz];
            sz--;
        }
        sz++;
    }
 
    ll query(ll x) {
        int lo = 0, hi = sz - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (cross(mid, mid + 1) <= x) lo = mid + 1;
            else hi = mid;
        }
 
        return la[lo] * x + lb[lo];
    }
}hull;
 
//소수점 처리
string mod[] = { ".00", ".25", ".50", ".75" };
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int tc; cin >> tc;
    while (tc--) {
        px.clear(); py.clear();
 
        int n; cin >> n;
        px.resize(n); py.resize(n);
 
        for (int i = 0; i < n; i++)
            cin >> px[i] >> py[i];
 
        //stack을 이용해 탐색하면서 필요없는 점들을 계산
        stack<int> stk;
        stk.push(0);
 
        for (int next = 1; next < n; next++) {
            int now = stk.top();
 
            double dx = cross(now, next);
 
            if (dx >= px[next]) {
                while (dx >= px[next]) {
                    stk.pop();
                    if (stk.empty()) break;
                    now = stk.top();
                    dx = cross(now, next);
                }
                stk.push(next);
            }
            else if (dx <= px[now]) {}
            else stk.push(next);
        }
 
        n = stk.size();
        lx.clear(); ly.clear();
        lx.resize(n); ly.resize(n);
 
        while (!stk.empty()) {
            int top = stk.top(); stk.pop();
            lx.push_back(px[top]); ly.push_back(py[top]);
        }
 
        reverse(lx.begin(), lx.end());
        reverse(ly.begin(), ly.end());
 
        //ConvexHull Trick 적용
        //주의할 점 점화식에 4를 나누어주므로 오차가 발생할 수 있음.
        //그러므로 4를 앞으로 빼고 나중에 결과에 4를 나누는 방식
        hull.Init();
        
        vector<ll> dp(n+1);
        hull.insert(-2 * (lx[0] - ly[0]), (lx[0] - ly[0]) * (lx[0] - ly[0]));
        for (int i = 0; i < n; i++) {
            ll u = lx[i] + ly[i];
            ll v = lx[i+1] - ly[i+1];
            dp[i] = hull.query(u) + u * u;
            hull.insert(-2* v, v* v + dp[i]);
        }
        
        cout << dp[n-1] / 4 << mod[dp[n-1]%4] << "\n";
    }
    return 0;
}