[백준] 1126 같은 탑

1126번: 같은 탑

문제 확인

 

dp 문제입니다.

left, right를 나누어 dp를 작성하면 dp[500000][500000]이 되므로 메모리 초과가 일어나기 때문에 | left-right | 를 기준으로 dp를 작성해야 합니다.

 

풀이

 

탐색 횟수를 줄이기 위해 입력 받은 수를 정렬하고 현재 단계에서 갈 수 있는 최댓값까지 탐색을 합니다.

조각을 쌓을 때 2가지 경우로 나눌 수 있습니다.

1. 높은 탑에 쌓기 : 높은 탑에 쌓는 경우 현재 dp[j] 를 가리키고 있으며 dp[j + ary[i]] 값에 최댓값이 저장됩니다.
2. 낮은 탑에 쌓기 : 이 경우 낮은 탑에 ary[i]를 쌓았을 때 옆의 탑보다 높아지는 경우가 있으므로 2가지 경우가 더 생깁니다.

 

1. j < ary[i] : 이 경우 낮은 탑이 더 높아지게 되므로 dp[ary[i] - j]를 가리키게 됩니다.
2. j > ary[i] : 반대로 dp[j - ary[i]] 가 됩니다.

따라서 점화식을 세워보면 다음과 같습니다.

dp[j + ary[i] = max(dp[j + ary[i], dp[0][j] + ary[i])

if (j < ary[i]) 
     dp[1][ary[i] - j] = max(dp[1][ary[i] - j], dp[0][j] + ary[i] - j);
else 
     dp[1][j - ary[i]] = max(dp[1][j - ary[i]], dp[0][j]);

 

주의해야 할 점은 dp 배열을 0~max_len 까지 작성한 후 다음 i 루프에서 사용해야 하므로 dp[2][500000]을 사용합니다.

 

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
#define mx(a,b)a>b?a:b
using namespace std;
int main() {
    int n;
    int ary[50], dp[2][500001];
    memset(dp, -1, sizeof dp);
    dp[0][0] = dp[1][0] = 0;
    
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &ary[i]);
    sort(ary, ary + n);
 
    for (int i = 0, max_len = 0; i < n; i++) {
        for (int j = 0; j <= max_len; j++) {
            if (dp[0][j] == -1)continue;
            dp[1][j + ary[i]] = max(dp[1][j + ary[i]], dp[0][j] + ary[i]);//높은 블록에 쌓기
            if (j < ary[i]) //낮은 블록에 쌓기
                dp[1][ary[i] - j] = max(dp[1][ary[i] - j], dp[0][j] + ary[i] - j);
            
            else 
                dp[1][j - ary[i]] = max(dp[1][j - ary[i]], dp[0][j]);
        }
        max_len += ary[i];
        memcpy(dp[0], dp[1], 4 * (max_len + 1));
    }
    printf("%d", dp[0][0] > 0 ? dp[0][0] : -1);
}