BOJ 1126 같은 탑

• solved ac class 7 essential

• 풀이
• Code

풀이

Dynamic programming 을 이용해서 어렵지 않게 해결할 수 있다. 다음과 같이 정의하자.

DP[i][j] : 1번부터 $i$번까지의 블록만 고려할 때, $H_A - H_B = j$ 가 되면서 만들 수 있는 $H_A$의 최대 높이

이렇게 정의하면, 크기가 $h$인 다음 블록을 추가할 때, A에 얹는 경우와 B에 얹는 경우를 나누어 생각할 수 있다. A에 얹는 경우에는, 차가 $j + h$ 로 늘어나면서 $H_A$의 크기도 실제로 늘어나고, B에 얹는 경우에는 차가 $j-h$로 줄어들면서 $H_A$의 크기는 그대로 유지된다. 같은 $j$일 때 $H_A$가 크면 자명하게 $H_B$가 커지기 때문에 이렇게 관리해도 충분함을 쉽게 알 수 있다.

다만 $j$의 범위가 $-500,000$ 에서 $500,000$이기 때문에, 실제로는 100만 칸의 DP를 잡아서 $j$ 대신 $j + 5e5$ 로 생각하고 움직이면 된다. 이렇게 관리하면 복잡도 $2 * n * \sum H$ 칸의 DP 테이블을 채우는 것이므로 시간 내에 잘 관리가 된다.

5천만 칸의 int를 잡고 싶지 않다면, 바로 직전 DP 테이블만 있으면 된다는 사실을 이용해서 100만 * 2개만 있으면 된다. 아래 코드는 그렇게 구현되어 있다. 이를 간혹 토글링이라고 부르는데, 구현에서는 토글링을 하지는 않았고 그냥 tmp에다가 매번 memset 하면서 가는데, 5천만 칸 memset정도는 라이브러리가 매우 빠르므로 그냥 믿어도 충분하다.

구현의 편의상, 0개의 블록을 써서 A = B = 0 을 만들 수 있다고 보는 것이 자연스럽다. 그러나 이는 실제로 불가능한 칸과 실제로 가능한 칸의 구분에 혼란을 주기 때문에, 나는 그냥 편하게 가상의 높이 1을 준 다음 나중에 빼 주는 식으로 구현했다. 결과적으로 다 짜고 보니 굳이 그럴 필요는 없었고, 첫 DP에서만 잘 처리해주는게 더 간단했을것 같기도 하다.

Code

#include <bits/stdc++.h>
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

int M = 500000;
int dp[1010101];
int tmp[1010101];
int32_t main()
{
    usecppio
    int n; cin >> n;
    dp[M] = 1;
    for (int i = 0; i < n; i++)
    {
        int h; cin >> h;
        memset(tmp, 0x0, sizeof(tmp));
        for (int j = 0; j <= 2*M; j++)
        {
            if (j >= h)
            {
                if (dp[j] > 0)
                    tmp[j - h] = max(tmp[j - h], dp[j]);
            }
            if (j + h <= 2 * M)
            {
                if (dp[j] > 0)
                    tmp[j + h] = max(tmp[j + h], dp[j] + h);
            }
        }
        for (int j = 0; j <= 2 * M; j++)
            dp[j] = max(dp[j], tmp[j]);
    }
    if (dp[M] <= 1)
        cout << -1 << '\n';
    else cout << dp[M] - 1 << '\n';
}