[백준/BOJ/1126] 같은 탑

1) 조각을 사용하지 않는 경우

2) 높은 탑에 놓는 경우

3) 낮은 탑에 놓는 경우 

 

낮은 탑에 놓는 경우는 아래 처럼 두 가지 경우로 나뉜다.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int N, arr[51], dp[51][250001];
int dfs(int k, int diff) {
	if (diff > 250000) return -1e9;
	if (k == N) {
		if (diff == 0) return 0;
		return -1e9;
	}
	int &ret = dp[k][diff];
	if (ret != -1) return ret;
	ret = dfs(k + 1, diff); // 사용 x
	ret = max(ret, dfs(k + 1, diff + arr[k])); // 높은 탑에 놓는 경우
	if (arr[k] > diff) {
		ret = max(ret, diff + dfs(k + 1, arr[k] - diff)); // 낮은 탑1
	}
	else {
		ret = max(ret, arr[k] + dfs(k + 1, diff - arr[k])); // 낮은 탑2
	}
	return ret;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < N; i++) cin>>arr[i];
	int res = dfs(0, 0);
	if (res == 0) cout << "-1\n";
	else {
		cout << res << "\n";
	}
	return 0;
}