/<1126> 같은 탑

새 블로그의 첫 풀이글이네요. 개인적으로 재밌었던 문제입니다. 풀이를 거히 다 떠올려놓고 엉뚱한 방향으로 새다가 지인이 “아니 그거 맞아” 라고 해줘서 풀긴 했지만… ㅋㅋㅋ… 유사 자력솔?

문제

주어진 높이의 블록들 $N$개 중 원하는 블록들을 골라서 사용해 높이가 같은 두개의 탑을 얼마나 높게 만들 수 있는지 물어보는 문제다. ($1 \le N \le 50$, $1 \le h_i \le 500\;000$, 모든 블록의 높이의 합은 $500\;000$을 넘지 않는다.)

풀이

가장 직관적인 풀이로 냅색을 생각해 볼 수 있다. $dp(i, H_1, H_2)$를 $i$ 번째 블록까지 블록들을 사용해서 1번 탑의 높이가 $H_1$이고 2번 탑의 높이가 $H_2$인 상태로 만들 수 있는지로 정의하면 된다 (가능하면 $1$ 반환 아니면 $0$ 반환). 답은 $1 \le H_1 \le 500,000$ 을 만족하는 $H_1$ 중 $dp(N, H_1, H_1) = 1$인 가장 큰 $H_1$이 된다.

하지만 이를 그대로 구현할 경우 최악 $50 \times 500,000 \times 500,000$ 만큼의 연산과 공간이 필요하다. 무언가 다른 발상이 필요함을 알 수 있다.

사실 우리가 문제의 상태공간을 정의 함에 있어서 $H_1$과 $H_2$가 뭔지는 별로 중요하지 않다.

문제를 다르게 생각해보면 우리가 찾고자 하는건 $\lvert H_1 - H_2 \rvert = 0$ 일때 가능한 가장 높은 높이이다. 이제 $dp$ 를 다르게 정의해 볼 수 있다.

$dp(i, \lvert H_1 - H_2 \rvert) = i$ 번째 블록까지 블록들을 사용해서 두 탑의 높이 차이가 $\lvert H_1 - H_2 \rvert$ 인 두 탑을 만들때 더 높은 탑의 높이중 최댓값.

따라서 이제 답은 $dp(N, 0)$이 된다.

$dp(i, w)$에서 가능한 상태 전이들을 생각해보자.

1. $dp(i, w)$이 불가능한 상태일 경우 전이는 불가능하다.
2. $h_i < w$ 라면 $dp(i+1, w-h_i) = \max(dp(i+1, w-h_i), dp(i, w))$ 이다. 더 낮은 탑에 $i$ 번째 블록을 올려 높이 차이를 줄였지만 대소 관계의 역전은 일어나지 않은 경우이다.
3. $h_i \ge w$ 라면 $dp(i+1, h_i-w) = \max(dp(i+1, h_i-w), dp(i, w) + h_i - w)$ 이다. 더 낮은 탑에 $i$ 번째 블록을 올려 대소 관계의 역전이 일어난 경우이다.
4. $dp(i+1, w) = \max(dp(i+1, w), dp(i, w))$ 이다. $i$ 번째 블록을 사용하지 않은 경우이다.
5. $dp(i + 1, w + h_i) = \max(dp(i + 1, w + h_i), dp(i, w) + h_i)$ 이다. 더 큰 탑에 $i$ 번째 블록을 올리는 경우이다. $w + h_i \le 500,000$ 등으로 답이 될 수 없는 차이로의 전이를 방지해야 한다.

이제 1~5의 과정을 코드로 구현하면 된다.

코드 (c++)

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

#define PRECISION 69

#define fr first
#define sc second

#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())

using ll = long long;
using ld = long double;

typedef pair<ll,ll> pll;
typedef pair<int,int> pii;

const int INF = 0x3f3f3f3f;
const ll LLINF = 4'500'000'000'000'000'000;
const ll MOD = 1'000'000'007;

int dp[55][505050]; // |a - b|

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);

    int N; cin >> N;
    vector<int>H(N + 1); for(int i=0; i<N; i++){
        cin >> H[i];
    }
    for(int i=0; i<=N; i++){
        for(int w=0; w<=500000; w++){
            dp[i][w] = -1;
        }
    }
    dp[0][0] = 0;

    for(int i=0; i<N; i++){
        for(int w=0; w<=500000; w++){
            if(dp[i][w] == -1) continue;
            if(H[i] < w){
                dp[i+1][w - H[i]] = max(dp[i+1][w - H[i]], dp[i][w]);
            } else {
                dp[i+1][H[i] - w] = max(dp[i+1][H[i] - w], dp[i][w] + H[i] - w);
            }
            dp[i+1][w] = max(dp[i+1][w], dp[i][w]);
            if(w + H[i] <= 500000) {
                dp[i+1][w + H[i]] = max(dp[i+1][w + H[i]], dp[i][w] + H[i]);
            }
        }
    }
    cout << (dp[N][0] <= 0 ? -1 : dp[N][0]);
}