🙇‍♀️가장 높은 탑 쌓기

밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다.

탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다.

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

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

▣ 입력설명
입력 파일의 첫째 줄에는 입력될 벽돌의 수가 주어진다.  

입력으로 주어지는 벽돌의 수는 최대 100개이다. 

둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차례대로 양의 정수로 주어진다. 

각 벽돌은 입력되는 순서대로 1부터연속적인 번호를 가진다. 

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

▣ 입력예제 1 
5
25 3 4
4 4 6
9 2 3
16 2 5
1 5 2

▣ 출력예제 1
10

🚀풀이

블록의 정보를 담을 구조체를 생성한다.

struct block
{
	int area;
	int height;
	int weight;

	bool operator<(const block& other) const
	{
		return area > other.area;
	}
};

구조체를 넓이 내림차순으로 정렬한다.

문제의 해결로직은 dp의 정의가 중요하다.
dp는 그 해당위치의 블록을 맨 위 블록으로 했을 때 최대 높이를 말한다.

그렇게 하기 위해서 문제의 조건들에 맞게 걸려줘야한다.

void solve()
{
	dp[0] = v[0].height;
	for (int i = 1; i < n; ++i)
	{
		int maxHeight = 0;
		for (int j = i - 1; j >= 0; --j)
		{
            // 아래에 무게가 낮은게 있으면 안된다.
            // 그 중 최대값을 찾아야한다.
			if (v[j].weight > v[i].weight && dp[j] > maxHeight)
			{
				maxHeight = dp[j];
			}
		}
        // 그 값을 찾으면 i번째 블록의 높이를 더해준다.
		maxHeight += v[i].height;
        // dp에 저장
		dp[i] = maxHeight;
        // dp중 최대값을 저장한다.
		res = max(res, dp[i]);
	}

	cout << res;
}

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

struct block
{
	int area;
	int height;
	int weight;

	bool operator<(const block& other) const
	{
		return area > other.area;
	}
};

int n, res = 0;
vector<block> v;
vector<int> dp;
void setting()
{
	cin >> n;
	dp = vector<int>(n + 1);
	for (int i = 0; i < n; ++i)
	{
		int a, b, c;
		cin >> a >> b >> c;
		v.push_back({ a, b, c });
	}

	sort(v.begin(), v.end());
}

void solve()
{
	dp[0] = v[0].height;
	for (int i = 1; i < n; ++i)
	{
		int maxHeight = 0;
		for (int j = i - 1; j >= 0; --j)
		{
			if (v[j].weight > v[i].weight && dp[j] > maxHeight)
			{
				maxHeight = dp[j];
			}
		}
		maxHeight += v[i].height;
		dp[i] = maxHeight;
		res = max(res, dp[i]);
	}

	cout << res;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	setting();
	solve();

	return 0;
}

참고