[BOJ] 1126 : 같은 탑 - travelbeeee

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

---

[ 코멘트 ]

1. DP 배열 정의가 도저히 생각나지않아, 구글링을 통해 DP 배열 정의만 참고함.

2. dp 배열을 -1로 초기화해야됨. 0으로 초기화해도 충분할 줄 알았지만, 0으로 초기화하면 새로운 막대만 사용하는 경우를 처리해줄 수가 없다. 따라서 -1로 초기화하고 dp[0][0] = 0, dp[0][top[0]] = top[0] 으로 초기값을 설정해야한다.

3. 

    if (dp[N - 1][0] == 0) 
        cout << -1;
    else 
        cout << dp[N - 1][0];

 위의 코드와 아래 코드는 다르게 작동한다... 이 부분 때문에 4시간은 날린 것 같다,,,

    cout << dp[N - 1][0] ? dp[N - 1][0] : -1;

 삼항 연산자를 사용하면 '?' 보다 출력 ' << ' 가 우선순위가 높기 때문에 dp[N - 1][0] 이 0이면 '-1'이 아니라 그냥 boolean 값 false가 출력된다.

 

[ 알고리즘풀이 ]

DP[ I ][ J ] = 0 ~ (i - 1)번 째 블록까지 사용해 두 개의 탑을 만들었고, 두 탑의 차이가 j일 때 큰 탑의 최대 높이.

DP 배열 정의부터 복잡하니 그림으로 이해해보자.

DP[ i - 1 ] [ J ] = K 라고 하자.

 그럼 0 ~ (i - 2)번 블록까지 사용해 위의 그림과 같은 상황이 만들어진 것이다.

 여기서 우리가 ( i - 1 )번 블록을 가지고 취할 수 있는 행동은 총 3가지다.

 

- 위의 상태를 그대로 둔다.

- (i - 1)번 블록을 왼쪽 더 높은 탑에다가 쌓는다. 그러면, 높이 차이랑 길이가 (i - 1)번 블록 길이 만큼 커진다.

- (i - 1)번 블록을 오른쪽 탑에다가 쌓는다.

 이때, 높이 차이 J 보다 (i - 1)번 블록이 크다면 오른쪽 탑이 더 높아지고 아니라면 여전히 왼쪽 탑이 더 높으므로 경우의 수를 나눠줘야한다.

			// 그대로두자 --> 변화없음.
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);
			// 탑의 큰 쪽에 쌓자. --> 차이가 j + top[i],  큰 탑이 dp[i - 1][j] + top[i];
			dp[i][j + top[i]] = max(dp[i][j + top[i]], dp[i - 1][j] + top[i]);
			// 탑의 작은 쪽에 쌓자. --> 경우의 수가 2가지.
			if (j < top[i]) // 탑의 최대가 바뀐다.
				dp[i][top[i] - j] = max(dp[i][top[i] - j], dp[i - 1][j] - j + top[i]);
			if (j >= top[i]) // 큰쪽이 계속 크다.
				dp[i][j - top[i]] = max(dp[i][j - top[i]], dp[i - 1][j]);

 위와 같은 점화식이 성립하고, 만약에 DP[ i - 1 ][ j ] 가 -1 이라면 애초에 조건을 만족하는 두 개의 탑이 존재하지 않으므로, 그냥 넘어간다.

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

int N, top[50], sum = 0;
int dp[50][500001]; // dp[i][j] : i번 째 조각까지 사용하고 두 탑의 높이 차가 j일 때, 큰 탑 높이의 최대값.

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> top[i];
		sum += top[i];
	}

	memset(dp, -1, sizeof(dp));

	dp[0][0] = 0;
	dp[0][top[0]] = top[0];
	for (int i = 1; i < N; i++) {
		for (int j = 0; j <= sum; j++) {
			if (dp[i - 1][j] == -1)
				continue;
			// 쌓지말자 --> 변화없음.
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);
			// 탑의 큰 쪽에 쌓자. --> 차이가 j + top[i],  큰 탑이 dp[i - 1][j] + top[i];
			dp[i][j + top[i]] = max(dp[i][j + top[i]], dp[i - 1][j] + top[i]);
			// 탑의 작은 쪽에 쌓자. --> 경우의 수가 2가지.
			if (j < top[i]) // 탑의 최대가 바뀐다.
				dp[i][top[i] - j] = max(dp[i][top[i] - j], dp[i - 1][j] - j + top[i]);
			if (j >= top[i]) // 큰쪽이 계속 크다.
				dp[i][j - top[i]] = max(dp[i][j - top[i]], dp[i - 1][j]);
		}
	}
	dp[N - 1][0] ? cout << dp[N - 1][0] : cout << -1;
	return 0;
}

---

내 6시간,,,