[BOJ 1126] 같은 탑

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

1126번: 같은 탑

 

- 문제 요약

 

홍준이는 N개의 직사각형 블록을 가지고 있다. 홍준이는 블록 위에 또 다른 블록을 올려놓는 방식으로 탑을 만들 수 있다. 이때, 두 개의 탑을 만드는데, 이 두 탑의 높이가 같게 만들려고 한다. 각 탑은 적어도 한 개의 블록을 포함해야 한다. 홍준이는 되도록이면 탑의 높이를 최대로 하려고 한다. 그리고 모든 블록을 사용할 필요는 없다.

각 블록의 높이가 주어질 때, 홍준이가 만들 수 있는 탑의 높이의 최댓값을 출력하는 프로그램을 작성하시오.

탑 만들기가 불가능할 때는 -1을 출력한다.

 

첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘지 않는다.

 

 

- 알고리즘 정리

 

dp[i][j] : i개의 블록을 사용해서 탑을 만들 경우, 두 탑의 길이차가 j일 때의 최댓값

 

DP 배열의 설정은 위와 같이 하고, 아래와 같이 케이스를 나눠서 메모이제이션으로 처리해 주면 풀 수 있습니다.

 

1. i번째 블록을 사용하지 않는 경우
2. 높이가 더 높은 탑에 블록을 놓는 경우
3. 높이가 더 낮은 탑에 블록을 놓는 경우

 

 

- 코드 작성

 

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

#define MAX 250000
#define INF 987654321
int n,arr[51],dp[51][MAX+1],result;

int f(int cur,int diff){
	if(diff>MAX){
		return -INF;
	}
	if(cur==n+1){
		if(diff==0){
			return 0;
		}
		else{
			return -INF;
		}
	}
	int &w=dp[cur][diff];
	if(w!=-1){
		return w;
	}
	w=f(cur+1,diff);
	w=max(w,f(cur+1,diff+arr[cur]));
	if(arr[cur]>diff){
		w=max(w,diff+f(cur+1,arr[cur]-diff));
	}
	else{
		w=max(w,arr[cur]+f(cur+1,diff-arr[cur]));
	}
	return w;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	memset(dp,-1,sizeof(dp));
	result=f(1,0);
	cout<<(result>0?result:-1);
}

코드 제출 결과