BOJ - 땅따먹기(6171)

플레티넘1 : 동적 계획법, Convex Hull 문제이다.

생각

일단 완전 탐색을 생각해 본다. 음.. 말도 안된다. 몇개를 겹쳐서 만드는지 완전탐색을 한다면 시간 복잡도가 $O(n!)$ 이다. 이 문제는 그냥 직관적으로 동적 계획법 냄새가 난다. 어떠한 조건에서 특정 위치까지의 땅의 최소값이 다음을 구하는데 영향을 줄 것 같기 때문이다.

정의

dp[n] = n번째 땅까지 구매했을 때 비용의 최솟값

이렇게 정의했다면, 이제는 점화식을 어떻게 세울지 고민해야 한다. n번째 땅까지 구매했을 때 비교해봐야 하는 값들을 나열해 보자.

1. n번째 땅을 그냥 산다. 그리고 n-1까지의 최소값과 더한다.
2. n-1번째 땅과 묶어서 계산해본다. 그리고 n-2까지의 최솟값과 더한다.
3. n-2번째 땅과 묶어서 계산해본다. 그리고 n-3까지의 최솟값과 더한다.

…

호오. 가능할 것 같은 냄새가 난다. 이렇게 할 경우 $O(n^2)$ 까지 줄일 수 있을 것 같다.

dp\[i\] = min\_{j=i}^{j=1}(dp\[j-1\] + \sum\_{k=j}^{k=i}a_k)

dp[i] = min(dp[j-1] + j부터 i까지의 땅을 합쳐 산 금액)

이 것을 수식으로 정리해보면, 위와 같다. 그렇다면 j부터 i가지의 땅을 합쳐 산 금액은 어떻게 구할까?

j부터 i가지의 땅을 합쳐 산 금액

실제로 땅을 사본다고 생각한다. 가장 빨리 직관을 얻는 것은 그림을 그려보는 것이다. 결국 이 문제는, 땅을 구입하는데 있어서 이걸 통짜로 한번에 사버린다는 얘기와 같다.

입력이 100 1, 20 20이 들어왔다고 생각하자. 이 부분에 해당하는 땅을 그리면 위와 같다. 그런데, 내가 이 두 땅을 합친다고 생각하면 결국 중요한 것을 최대 너비와 최대 높이이다. 아까 위에서 본 것처럼 결국 dp[i]을 구하기 위해서는 맨 아래 땅부터 포함해서 위쪽 땅을 1개, 2개 3개 … 를 선택하여 합쳐야 한다. 그렇다면, 땅을 합치는 데 있어서 3개를 합친다면, 3개의 땅의 너비와 높이를 다 비교해서 얻어내야 하는데.. 굳이 그래야 할까?

정렬하기

굳이 그럴 필요 없다. dp[i]을 구하는데 있어서 무조건 포함해야 하는 땅은 i번째 땅이다. 그렇다면 내가 합치고 싶은 범위의 땅은 j번째 땅이다. 이 두땅을 각각 ground[i], ground[j] 라 하겠다.

땅을 구하는데 있어서 위의 문제처럼 일일히 최댓값을 구하지말고, 이렇게 하면 좋겠다.

ground[i] = 합칠 땅의 최대 height

ground[j] = 합칠 땅의 최대 width

이러면, 시간 복잡도 $O(1)$에 가능하다..!

필요없는 땅 제거

그런데 정렬을 하다보니 이런 땅도 있다.

음.. 이런 땅은 어쩌지? 잘 생각해보면, 이 땅은 필요없다. 이미 땅을 살 때, 포함되는 땅이기 때문이다. 예를 들어 20 20을 구매한다면, 15 15는 합쳐살 경우 자연스레 구매하게 되는 땅이다. 합쳐사지 않는 다면 오히려 비용만 늘기 때문에 결국 이 땅은 최소값을 구하는데 도움이 되지 않는 땅이다. 또한 이 땅을 배열에 갖고 있게 된다면, 우리가 위에서 만들고 싶은 정렬 규칙에 위배되므로써 상수시간 안에 구하는 것이 어려워진다. 따라서 이런 조건에 해당하는 땅은 제거한다.

정렬한 땅에서, 지금 땅의 높이보다 다음 땅의 높이가 크면 추가한다.

점화식

dp[i] = min(dp[j-1] + (ground[j].w * ground[i].h)) > (단, i >= j >= 1)

Code

#include<iostream>
#include<vector>
#include<string>
#include <algorithm>
using namespace std;
 
typedef long long ll;
struct Square {
    ll w, h;
};
 
int N;
vector<Square> temp;
vector<Square> ground;
vector<ll> dp;
 
bool compare(Square a, Square b){
    if (a.w == b.w) return a.h < b.h;
    return a.w > b.w;
}
 
int main(){
    cin >> N;
    temp.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> temp[i].w >> temp[i].h;
    }
    sort(temp.begin(), temp.end(), compare);
 
    ground.push_back(temp[0]);
    ground.push_back(temp[0]);
    for (int i = 1; i < N; i++) {
        Square next = temp[i];
        Square now = ground.back();
        if (next.h > now.h) ground.push_back(next);
    }
 
    int size = int(ground.size());
    dp.resize(size);
 
    for (int i = 1; i < size; i++) {
        dp[i] = dp[i-1] + ground[i].w * ground[i].h;
        for (int j = i; j > 0; j--) {
            dp[i] = min(dp[i], dp[j-1] + (ground[j].w * ground[i].h));
        }
    }
    cout << dp[size-1] << '\n';
    return 0;
}

Convex Hull

하지만.. 플레티넘의 위엄이 있다. 이렇게 풀면 시간초과가 난다. 당연히 입력이 1000000이기 때문에 최악의 경우 $O(n^2)$ 이다. 그래서 여기서는 추가적인 최적화가 필요하다.

Reference

• 백준(6171번) - 땅따먹기