[BOJ 6599 // C++] The Tower of Babylon

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 6599번 문제인 The Tower of Babylon이다.
문제는 아래 링크를 확인하자.

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

6599번: The Tower of Babylon

회전을 고려하지 않을 때, 밑면의 가로와 세로가 각각 x,y인 블럭 B가 바닥인 탑의 최대 높이는 B보다 가로와 세로가 모두 작은 각 블럭 b에 대하여 "블럭 b가 바닥인 탑의 최대높이"의 최댓값 + z로 구할 수 있다.

 

위와 같은 점화관계를 이용해 dp로 문제를 해결하자.

 

블럭의 회전을 따로 고려하기 귀찮으므로, 전체 블럭목록에 (x,y,z)의 6가지 순열을 모두 집어넣어 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
using namespace std;

struct block {
	int x, y, z;
	block() {};
	block(int x, int y, int z) {
		this->x = x, this->y = y, this->z = z;
	}
};

int N;
block B[180];
int dp[180];

int func(int idx) {
	if (dp[idx]) return dp[idx];
	auto& cur = B[idx];
	for (int i = 0; i < N; i++) {
		auto& nxt = B[i];
		if (nxt.x < cur.x && nxt.y < cur.y) dp[idx] = max(dp[idx], func(i));
	}
	return dp[idx] = dp[idx] + cur.z;
}

int casenum = 0;

void solve() {
	memset(dp, 0, sizeof(dp));
	casenum++;

	for (int i = 0; i < N; i++) {
		int x, y, z; cin >> x >> y >> z;
		B[6 * i] = block(x, y, z);
		B[6 * i + 1] = block(x, z, y);
		B[6 * i + 2] = block(y, x, z);
		B[6 * i + 3] = block(y, z, x);
		B[6 * i + 4] = block(z, x, y);
		B[6 * i + 5] = block(z, y, x);
	}
	N *= 6;

	int ans = 0;
	for (int i = 0; i < N; i++) ans = max(ans, func(i));

	cout << "Case " << casenum << ": maximum height = " << ans << '\n';
}

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

	cin >> N;
	while (N) {
		solve();
		cin >> N;
	}
}