[BOJ 1126] 같은 탑

문제

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

1126번: 같은 탑

 

---

알고리즘

• DP
• 배낭 문제
• 슬라이딩 윈도우 (optional)

---

풀이

\(N\)개의 직사각형 블록을 이용하여 만든 높이가 같은 두 탑의 높이가 최대가 되게 해야 하며, 모든 직사각형 블록을 다 사용할 필요는 없습니다. 즉, \(i\)번째 직사각형 블록을 쌓거나 쌓지 않거나로 나눌 수 있습니다.

그러므로, \(dp[i][j]\)를 다음과 같이 정의할 수 있습니다:

 

• \(dp[i][j]:\) \(i\)번째 직사각형 블록까지 고려했고, 두 탑의 높이의 차이가 \(j\)일 때, 두 탑중 높이가 더 작은 탑의 높이의 최댓값.

\(i\)번째 직사각형 블록을 쌓는 경우를 생각하면 \(1\)번째 탑 위에 쌓거나 \(2\)번째 탑 위에 쌓는 경우로 또 나눌 수 있습니다.

그러므로, \(dp[i][j]\)에 대해서는 다음 \(4\)가지 경우를 생각할 수 있습니다:

 

1. \(i\)번째 직사각형 블록을 쌓지 않았을 때
2. \(i\)번째 직사각형 블록을 높이가 더 큰 탑에 쌓았을 때
3. \(i\)번째 직사각형 블록을 높이가 더 작은 탑에 쌓고 쌓은 후의 높이도 더 작을 때
4. \(i\)번째 직사각형 블록을 높이가 더 작은 탑에 쌓고 쌓은 후의 높이가 더 커졌을 때

따라서, \(i\)번째 직사각형 블록의 높이를 \(A_{i}\)라고 할 때, \(dp[i][j]\)에 대한 점화식을 다음과 같이 세울 수 있습니다:

$$dp[i][j] = max\begin{cases}
dp[i - 1][j]\\
dp[i - 1][j + A_{i}] + A_{i}\\
dp[i - 1][j - A_{i}]\\
dp[i - 1][A_{i} - j] + A_{i} - j\\
\end{cases}$$

두 탑의 높이가 같아야 하므로, \(dp[N][0]\)이 \(0\)이면 \(-1\), 아니면 그 값을 출력하면 됩니다.

 

시간복잡도: \(O(NM)\)

 

---

코드

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;

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

int N, arr[51], dp[51][500001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= N; ++i) cin >> arr[i];
    dp[0][0] = 0;
    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j <= 500000; ++j) {
            dp[i][j] = dp[i - 1][j];
            if (j + arr[i] <= 500000 && dp[i - 1][j + arr[i]] != -1)
                dp[i][j] = max(dp[i][j], dp[i - 1][j + arr[i]] + arr[i]);
            if (j - arr[i] >= 0 && dp[i - 1][j - arr[i]] != -1)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - arr[i]]);
            if (arr[i] - j >= 0 && dp[i - 1][arr[i] - j] != -1)
                dp[i][j] = max(dp[i][j], dp[i - 1][arr[i] - j] + arr[i] - j);
        }
    }
    if (!dp[N][0]) cout << "-1\n";
    else cout << dp[N][0] << '\n';

    return 0;
}

 

각 \(i\)에 대해서 확인하는 값은 \(i, i - 1\) 두 개 뿐이므로, 슬라이딩 윈도우를 사용해 메모리를 줄일 수 있습니다.

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    const int MXM = 500000;
    int N, dp[2][MXM + 1];
    memset(dp, -1, sizeof(dp));
    cin >> N;
    for (int i = 1; i <= N; ++i) {
        int hgt, n = i % 2;
        cin >> hgt;
        fill(dp[n], dp[n] + MXM, -1);
        if (dp[!n][0] == -1) dp[!n][0] = 0;
        for (int j = 0; j <= MXM; ++j) {
            dp[n][j] = dp[!n][j];
            if (j + hgt <= MXM && dp[!n][j + hgt] != -1)
                dp[n][j] = max(dp[n][j], dp[!n][j + hgt] + hgt);
            if (j - hgt >= 0 && dp[!n][j - hgt] != -1)
                dp[n][j] = max(dp[n][j], dp[!n][j - hgt]);
            if (hgt - j >= 0 && dp[!n][hgt - j] != -1)
                dp[n][j] = max(dp[n][j], dp[!n][hgt - j] + hgt - j);
        }
    }
    if (!dp[N % 2][0]) cout << "-1\n";
    else cout << dp[N % 2][0] << '\n';

    return 0;
}