[BOJ 1126] 같은 탑

BOJ

[BOJ 1126] 같은 탑

gcmango 2021. 6. 23. 20:21

문제

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

1126번: 같은 탑

첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘

www.acmicpc.net

알고리즘

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

풀이

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

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

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

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

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

$i$번째 직사각형 블록을 쌓지 않았을 때
$i$번째 직사각형 블록을 높이가 더 큰 탑에 쌓았을 때
$i$번째 직사각형 블록을 높이가 더 작은 탑에 쌓고 쌓은 후의 높이도 더 작을 때
$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;
}