#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의 값이 해당 블록을 가지고 가장 높이 쌓은 높이이기 때문이다.