백준 6171 - 땅따먹기 (C++)

문제

• 문제 링크

  
   BOJ 6171 - 땅따먹기 
  

• 문제 요약

$N$개의 땅의 $W_i, H_i$가 주어진다.
문제에 정의된 구매 규칙을 따를 때, 모든 땅을 사는 최소 비용을 구해보자.

• 제한

TL : $1$ sec, ML : $128$ MB




$1 ≤ N ≤ 50,000$

$1 ≤ W_i, H_i ≤ 1,000,000$

알고리즘 분류

• 다이나믹 프로그래밍(dp)
• 볼록 껍질을 이용한 최적화(convex hull trick)

풀이

문제의 규칙을 따르면 임의의 부분 집합 땅(k개)을 살 때

$max(W_1, W_2, ... W_k) * max(H_1, H_2, ... H_k)$

의 비용이 발생 한다고 한다.

이는 결국 부분 집합에서 $W_1 >= W_2$ && $H_1 ≥ H_2$ 이면 2번 땅은 애초에 고려될 필요가 없다는 것이다.
이를 통해 다음의 전처리를 생각해 볼 수 있다.

• 일단 $W$던 $H$던 하나를 기준으로 잡고 내림차순 정렬을 한다. ( $W$를 기준으로 했다고 가정)
• $W$는 인덱스가 증가함에 따라 단조 감소 함이 보장되지만, $H$는 알 수 없다.
• 그러나 문제의 구매 조건에 의해 $i < j$ && $H_i ≥ H_j$을 만족하는 땅 $j$는 고려할 필요가 없다.
• 따라서 $i < j$ && $H_i < H_j$인 땅만 보면 된다.

이는 정렬 $O(N * log N)$ 후 $O(N)$만에 수행할 수 있다.

---

그렇게 추려낸 땅들로 이루어진 $V$에 맞게 $N$을 $resize$ 해주자.

$dp[i] : i$번까지의 땅을 적절히 묶어 살 수 있는 최소 비용. 로 정의 내린다면

$dp[i] = min(dp[i], dp[j - 1] + V[j].W * V[i].H)$ {$0 ≤ j ≤ i$}

와 같이 정리할 수 있다.

이때 $V$에서, $W$는 단조 감소 한다. 또, $H_i < H_j$인 땅만 추가 했으니 $H$는 단조 증가 한다.
$H(i)$를 $x$로 두고 $0 ≤ j ≤ i$인 $j$에 대한 일차 함수로 표현하면

$f(x) = W(j) * x + C$ 가 되고 단조 감소하는 함숫값에 대해 이분 탐색을 적용하여 $O(N log N)$으로 문제를 해결할 수 있다.

전체 코드

#include<bits/stdc++.h>
#define ll long long
#define N 50001
#define W first
#define H second
using namespace std;
 
struct S
{
    ll p, q;
    double d;
    bool operator<(int x) { return d < x; }
}ln[N];
vector <pair<int, int>> V;
pair<int, int> a[N];
ll n, u, i, dp[N];
 
inline double f(S& l, S& r) { return (r.q - l.q) / (l.p - r.p); }
void in()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (; i < n; i++)
        cin >> a[i].W >> a[i].H;
    sort(a, a + n, greater<>());
    V.emplace_back(a[0]);
    for (i = 1; i < n; i++)
        if (a[i].H > V.back().H)
            V.emplace_back(a[i]);
    n = V.size();
}
void sv()
{
    dp[0] = V[0].W * V[0].H;
    ln[u++] = { V[0].W, 0, 0 };
    for (i = 1; i < n; i++)
    {
        S t({ V[i].W, dp[i - 1], 0 });
        while (u)
        {
            t.d = f(t, ln[u - 1]);
            if (t.d > ln[u - 1].d) break;
            u--;
        }
        ln[u++] = t;
        ll j = lower_bound(ln, ln + u, V[i].H) - ln - 1;
        dp[i] = ln[j].p * V[i].H + ln[j].q;
    }
    cout << dp[n - 1];
}
int main()
{
    in();
    sv();
}

comment

끝