[백준] 1126 같은 탑

문제 링크

http://icpc.me/1126

1126번: 같은 탑

풀이

dp문제다. dp인 것을 못 알아차리고 고민하다가 알고리즘 분류를 봤다.

처음 생각했던 점화식은 dp[i][a_size][b_size] : i번째 까지 봤을 때 a기둥의 사이즈와 b기둥의 사이즈로 dp를 정의하는 것이었다.

그러나 이 풀이는 52 * 5e5 * 5e5로 시간초과가 발생할 것이다.

그래서 a기둥과 b기둥의 높이를 더 컴팩트하게 정의할 수 있는 방법을 생각했다.

결론은 더 큰 기둥의 높이와 작은 것과 큰것의 높이차만 알면 됐다.

dp[i][diff] : i번째까지 봤을 때 큰 것과 작은 것의 높이차가 diff인 것 중 큰 것의 최댓값

위와 같이 정의하면 i+1번째는 i번째에서 아무것도 선택하지 않을때, 더 큰 기둥에 i번째 조각을 쌓을 때, 더 작은 것에 i번째 조각을 쌓을 때로 나눌 수 있다.

코드

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

int arr[52], dp[52][500005], n; 

int dpf(int cur, int diff) {
    int &ret = dp[cur][diff];
    if (ret) return ret;
    if (cur == n) {
        if (diff) return -1e9;
        return 0;
    }
    return ret = max({
        dpf(cur + 1, diff), 
        dpf(cur + 1, diff + arr[cur]) + arr[cur], 
        dpf(cur + 1, abs(diff - arr[cur])) + (diff - arr[cur] < 0 ? arr[cur] - diff : 0)
    });
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
    int ans = dpf(0, 0);
    printf("%d", ans ? ans : -1);
}