[BOJ 1126] 같은 탑

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

 DP문제이다. 해당 문제의 경우 가능한 연산이 총 3가지이다.

(1) 첫번째 블럭에 넣기 (큰쪽에 둔다는 의미)

(2) 두번째 블럭에 넣기

(3) 그냥 버리기 

 이 3가지 연산을 수행하게 되는데 두 블럭의 높이 차이를 기록하고 그 중 높은쪽을 생각하게 된다. 만약 n번째까지 다 쌓았을때 그 둘의 차이가 0이 되게 되면 두 블럭의 높이가 같다고 볼 수 있다. 문제의 조건에서 모든 블럭의 합이 50만을 넘지 않는다고 하였기 때문에 dp배열은 n*250000으로 생각할 수 있다. 

 (3)번 연산은 36번째 줄 , (1)번 연산은 37번째 줄 , (2)번이 문제인데 만약 두려는 블럭의 크기가 두 블럭 사이의 높이 차 이상,이하일 때를 나누어서 생각해 볼 수 있다. 

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <set>
#include <queue>
#include <stack>
#define MAX_N 50
#define INF 1e8
 
typedef long long ll;
 
using namespace std;
 
int n,dp[MAX_N+1][255555],arr[MAX_N+1],ans,sum;
 
 
int solve(int pos,int diff){      //n개 사용했을때 차이 diff
    if(diff>250000)
        return -INF;
    
    if(pos == n){
        if(diff == 0){
            return 0;
        }else{
            return -INF;
        }
    }
    int &ret = dp[pos][diff];
    
    if(ret!= -1)
        return ret;
    
    ret = solve(pos+1,diff);         // 해당경우 그냥 버리는 경우
    ret = max(ret, solve(pos+1,diff+arr[pos]));
    
    if(arr[pos] > diff){
        ret = max(ret , diff+ solve(pos+1,arr[pos]-diff));
    }else{
        ret = max(ret , arr[pos]+solve(pos+1,diff-arr[pos]));
    }
    return ret;
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    
    for(int i=0;i<n;i++){
        cin >> arr[i];
    }
        memset(dp,-1,sizeof(dp));
    int ans = solve(0,0);
    
    if(ans == 0){
        cout << "-1\n";
    }else{
        cout << ans<<"\n";
    }
    
    
    return 0;
}