boj, 백준 ) 1126. 같은 탑(C / C++)

1. 문제 링크

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

1126번: 같은 탑

2. 문제 개요

N개의 직사각형 블록을 가지고 있다. 블록 위에 또 다른 블록을 올려놓는 방식으로 탑을 만들 수 있다.

두 개의 탑을 만드는데, 이 두탑의 높이가 같게 만들려고 한다. (각 탑은 적어도 한 개의 블록을 포함해야 한다)

그리고 모든 블록을 사용할 필요는 없다.

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

 

3. 문제 힌트

dp는 어떻게 설계해야할까?

처음에 dp[개수][높이][높이]로 하려고 했는데 50만이라 불가능하다는 걸 알았다.

그리고 [개수][왼쪽 가장 위 블록][오른쪽 가장 위 블록]으로 생각해봐도 도중에 사용하지 않는 블록이 있는 데다가 섞일 수 있기 때문에 안된다는 걸 깨달았다.

 

그래서 [개수][높이차이]로 설계를 했다. 이 부분은 쉽게 생각이 나질 않아 다른 사람의 풀이를 조금 참고했다.

dp[n][diff]로 설계를 하고, 각 dp 배열이 갖는 값은 n개를 사용해서 두 블록의 길이 차가 diff일 때, 최댓값이라고 한다.

 

그렇다면 구현은 어떻게 해야 할까?

n번째 블록을 쓰지 않는 경우.

둘 중 긴 곳에 놓는 경우.

둘 중 낮은 곳에 놓는 경우.

이렇게 3가지 경우가 있겠다.

 

4. 문제 풀이

 

이 문제를 DP를 사용하지 않고 푼다면..

3가지 경우의 최대 50개가 있으므로 O(3^50)이 될 것이다.

따라서.. 최대 25만 개 사이즈의 배열을 추가하면서 시간 복잡도를 줄일 것이다.

 

(3) 번에서 dp배열을 설계했으므로 여기서 구현 부분을 보면,

 

① diff 두 블록의 차이가 25만이 넘으면 같아질 수 없다.

② 끝에 도달했을 때 diff가 0인지 체크해야 함.

③ 메모이제이션

④ (3)에서 말한 3가지로 넘어가기

 

여기서 주의할 점을 보자.

 

②번에서 diff == 0이면 0을 return 한다.

만약에 diff != 0 이면 음의 엄청 큰 수 를 return 해주어야 한다.

 

④번에서 주의할 점은 차이가 줄어들 때이다.

차이가 줄어들 때 diff보다 이번에 놓을 블록이 더 크다면  새로운 차이는 (놓을블록 - diff)가 되고, diff만큼 두 탑의 공통부분이 늘어난다.

차이가 줄어들때 diff가 이번에 놓을 블록보다 크다면 새로운 차이는 (diff-놓을 블록)이 되고 ,  놓을 블록만큼 두 탑의 공통부분이 늘어난다.

 

여기서 원래대로라면 공통부분으로 계산하면 안 된다. 블록의 단위길이가 1이 아니고 각각 블록마다 길이가 다르기 때문이다. 하지만 이 부분은 ②에서 해결해줄 수 있다. diff가 0이면 결국 끝에서 길이가 같아짐을 의미하고, 맨 마지막에서 diff가 0이 아닌 것은 같지 않기 때문에 -INF를 반환하고,  길이를 조금 더해도 -INF이기 때문에 무시 가능하다.

 

그래서 해당 dp[n][diff]에서는 3가지 경우중 max값을 취해서 항상 최댓값을 유지할 수 있도록 한다.

 

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int n;
int dp_table[51][250001];	
int arr[51];

int dp(int cur, int diff)
{
	if (diff > 250000)
		return -987654321;

	if (cur == n + 1) {
		if (diff == 0)
			return 0;
		else
			return -987654321;
	}

	//memoization
	int &cache = dp_table[cur][diff];
	if (cache != -1)	return cache;
	

	
	cache = dp(cur + 1, diff);
	cache = max(cache, dp(cur + 1, diff + arr[cur]));	
	
	if (arr[cur] > diff) 
		cache = max(cache, diff + dp(cur + 1, arr[cur] - diff));
	else
		cache = max(cache, arr[cur] + dp(cur + 1, diff - arr[cur]));
	
	
	return cache;
	
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d", &arr[i]);

	memset(dp_table, -1, sizeof(dp_table));
	
	int ans = dp(1, 0);
	printf("%d", ans > 0 ? ans : -1);

	return 0;
}

 

6. 결과 사진

 

지적, 댓글 언제나 환영입니다~