[C++] 가장 높은 탑 쌓기 🔥

📄문제

밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다.

 

아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오.

(조건1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.
(조건2) 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다.
(조건3) 벽돌들의 높이는 같을 수도 있다.
(조건4) 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.
(조건5) 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.

 

⬇️ 입력

입력 파일의 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차례대로 양의 정수로 주어진다. 각 벽돌은 입력되는 순서대로 1부터연속적인 번호를 가진다.

5 25 3 4 4 4 6 9 2 3 16 2 5 1 5 2

 

⬆️ 출력

첫 번째 줄에 가장 높이 쌓을 수 있는 탑의 높이를 출력한다.

10

 

📝 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int dp[100];

struct brick
{
	int width;
	int height;
	int weight;

	brick() {}
	brick(int width, int height, int weight) : width(width), height(height), weight(weight) {}

	const bool operator < (const brick& ref) const
	{
		return width > ref.width;
	}
};

int main()
{
	ios_base::sync_with_stdio(false);

	int N, width, height, weight, res = INT_MIN;
	cin >> N;

	vector<brick> bricks(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> width >> height >> weight;
		bricks[i] = brick(width, height, weight);
	}

	// 가로 길이를 기준으로 정렬
	sort(bricks.begin(), bricks.end());

	dp[0] = bricks[0].height;

	// 이제부터는 무게를 기준으로만 계산
	for (int i = 1; i < N; ++i)
	{
		int max = bricks[i].height;
		for (int j = i - 1; j >= 0; --j)
		{
			// 아래 벽돌의 무게가 더 무거워야함
			if (bricks[i].weight < bricks[j].weight)
			{
				if (max < dp[j] + bricks[i].height)
					max = dp[j] + bricks[i].height;
			}

			dp[i] = max;
			if (dp[i] > res)
				res = dp[i];
		}
	}

	cout << res;
}

• 이 문제를 해결하기 위해 "가장 긴 증가하는 부분 수열"을 활용하였습니다.
• 벽돌을 쌓기 위한 조건이 두개가 있기에 하나는 미리 정렬을 하여 나머지 조건만 수열을 통해 계산할 수 있도록 하였습니다.
• 가로 길이는 정렬이 되었으니, 무게를 기준으로 계산하여 무게 조건이 맞는다면, 높이를 지속적으로 갱신하여 최대 높이로 쌓을 수 있는 곳을 찾아 출력합니다.