백준(BOJ) 1126 같은 탑 ***

이 문제는 설계하는데 시간이 오래걸렸다.
다른 디피 문제에 비해 기준으로 잡을 값을 무엇으로 정할지가 어려운 문제였다.

많은 시간 생각한 결과 차이를 이용하여 값을 저장 하지 않으면 안된다는 생각을 하였다.

설계를 다하였다면 코드는 금방 짤 수 있다.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <list>
#include <utility>
#include <functional>
#define MAX 500001
#define INF 987654321
#define MOD 1000000
typedef long long ll;
#pragma warning(disable:4996)
using namespace std;

int n,tmp,ans=-1,map[51],dp[51][MAX];
int main()
{
    fill_n(&dp[0][0],MAX,0);
    
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
        scanf("%d", &map[i]);
    for(int i=1;i<=MAX;i++)
        dp[0][i] = -1;
    
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=MAX;j++)
        {
            dp[i][j] = dp[i-1][j];
            if(j - map[i] >= 0 && dp[i-1][j-map[i]] != -1)
                dp[i][j] = max(dp[i][j], dp[i-1][j-map[i]] + map[i]);
            if(map[i] - j >= 0 && dp[i-1][map[i]-j] != -1)
                dp[i][j] = max(dp[i][j], dp[i-1][map[i]-j] + j);
            if(j + map[i] <= MAX && dp[i-1][j+map[i]] != -1)
                dp[i][j] = max(dp[i][j], dp[i-1][j+map[i]]);
        }
    }
    if(dp[n][0]!=0)
        printf("%d",dp[n][0]);
    else
        printf("-1");
    return 0;
}