95. 가장 높은 탑 쌓기 (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★☆☆

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int dy[100];

struct Block
{
	int r;
	int h;
	int m;
	
	Block(int x, int y, int z)
	{
		this -> r = x;
		this -> h = y;
		this -> m = z;
	}
	
	bool operator<(const Block &a) const
	{
		return r > a.r;
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, a, b, c, res = 0;
	cin >> n;
	
	vector<Block> V;
	
	for(int i = 0; i < n; i++)
	{
		cin >> a >> b >> c;
		V.push_back(Block(a, b, c));
	}
	
	sort(V.begin(), V.end());
	
	Block first = V[0];
	dy[0] = first.h;
	
	for(int i = 1; i < n; i++)
	{
		Block block = V[i];
		int max = 0;
		for(int j = i-1; j >= 0; j--)
		{
			Block temp = V[j];
			if(temp.m > block.m && dy[j] > max)
			{
				max = dy[j];
			}
		}
		dy[i] = max + block.h;
		if(dy[i] > res) res = dy[i];
	}
	
	cout << res << "\n";
	
	return 0;
	
}

1. 넓이 기준으로 연산자 오버로딩을 이용해 내림차순으로 정렬한다.

2. 0번 블록부터 시작해서 해당 블록이 가장 맨 위에 있다는 가정하에 그 블록의 바로 아래 블록을 찾아 그 높이를 dy에 더하면 된다. 다만, 넓이를 기준으로 내림차순으로 정렬했기 때문에 그 블록의 넓이보다 작은 블록은 볼 필요없다. 즉 해당 인덱스보다 큰 인덱스의 값은 확인할 필요가 없다.

• 0번 블록
  • 0번 블록 1개이므로
  • dy[0] = 3
• 1번 블록
  • 0번 블록의 무게가 1번 블록의 무게보다 가벼우므로
  • dy[1] = 2
• 2번 블록
  • 0번, 1번 블록이 둘 다 2번 블록 아래에 놓일 수 있다. 그 중 가장 높이가 높은 0번 블록을 아래에 둔다.
  • dy[2] = 3 + 2 = 5
• 3번 블록
  • 0번, 1번, 2번 블록 모두 무게가 3번 블록보다 가벼우므로
  • dy[3] = 4
• 4번 블록
  • 0번, 1번, 2번, 3번 블록을 아래에 둘 수 있다. 그 중 가장 높이가 높은 3번 블록을 아래에 둔다.
  • dy[4] = 5 + 5 = 10

위에서 언급한 "가장 높이가 높은" 은 dy의 값을 의미한다. dy의 값이 해당 블록을 가지고 가장 높이 쌓은 높이이기 때문이다.