[백준] 1126 - 같은 탑 (c++)

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

 

문제 요약

블록 N개의 길이가 주어진다. 블록으로 높이가 같은 두 탑을 만들 때 최대 높이를 구해라. 

*블록을 모두 사용하지 않아도 된다.

 

풀이 (N*1e6)

• DP

dp[n][1e6]  dp[i][j] = i블록까지 사용했고 두 탑의 높이 차가 j일때 더 높은 탑의 높이 로 정의하고 채워주면 된다. -1로 초기화를 하고 불가능한 경우는 continue 했다. 블록을 쓰지 않아도 되기 때문에 dp[i-1][j]->dp[i][j]로 전파를 해준다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define mid (st+en>>1)

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;cin>>n;
    vector<vector<int>> dp(n+1,vector<int>(1+5e5,-1));
    dp[0][0]=0;
    vector<int> v(n);
    for(int&x:v)cin>>x;
    for(int i=1,x;i<=n;i++) {
        x=v[i-1];
        for(int j=0;j<=5e5;j++) {
            if(!~dp[i-1][j])continue;
            dp[i][j]=max(dp[i][j],dp[i-1][j]);
            dp[i][j+x]=max(dp[i][j+x],dp[i-1][j]+x);
            if(x>j)
                dp[i][x-j]=max(dp[i][x-j],dp[i-1][j]+x-j);
            else
                dp[i][j-x]=max(dp[i][j-x],dp[i-1][j]);
        }
    }
    cout<<(dp[n][0]<=0?-1:dp[n][0]);
}