백준 1126 / C++

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

1126번: 같은 탑

 

[ 풀이 ] 

dp를 세워보자. 우선 인덱스는 필수조건이다. 그리고 높이를 알아야 하는데 두개의 높이를 모두 저장할 수 없다.

한 개의 높이만을 저장한다면 나머지 역시 알 수 없다. 높이의 차이를 저장하면 깔끔하게 해결된다. 

dp[i][j]를 i번 블록을 선택할지 정하려하고 현재 높이차가 j일 때 두개의 높이중 큰 값이라고 정의하자. 

상태전이는 3가지이다.

1. i번 블록을 선택하지 않는다. 

2. 선택후 더 큰 높이에다가 블록을 쌓는다.

3. 선택후 더 작은 높이에다가 블록을 쌓는다. 

이 때 식을 살펴보자.

1번식은 dp[i+1][j]이다.

2번식은 h[i] + dp[i+1][j+h[i]]이다.

3번식은 2가지로 나뉜다. 만약 지금 높이차보다 블록의 높이가 작다면, 블록을 쌓을경우 높이차는 j-h[i]가 된다.

또한 최대높이는 변함없다. 따라서 dp[i+1][j-h[i]]로 전이된다.

만약 지금 높이차보다 블록의 높이가 크다면, 블록을 쌓을 경우 높이차는 h[i]-j가 된다.

최대높이는 h[i]-j만큼 높아진다. 따라서 h[i]-j+dp[i+1][h[i]-j]로 전이된다. 

이 4가지중 최댓값을 계속 갱신해주면 된다.

 

[ Code ]

#include <bits/stdc++.h>
using namespace std;
int n, dp[55][250005], h[55];

// dp[i][j]
int go(int i, int j) {
	if (j > 250000) return -1e9; // base 1
	if (i == n) return j ? -1e9 : 0; // base 2 
	int& ret = dp[i][j];
	if (~ret) return ret;
	ret = -1e9;
	ret = max(go(i + 1, j), h[i] + go(i + 1, j + h[i])); // always 
	if (j >= h[i]) ret = max(ret, go(i + 1, j - h[i]));  // j>=h[i]
	else ret = max(ret, h[i] - j + go(i + 1, h[i] - j)); // j<h[i]
	return ret;

}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> h[i];
	memset(dp, -1, sizeof(dp));
	int ans = go(0, 0);
	cout << (ans ? ans : -1) << '\n';
}