[c++] 가장 높은탑쌓기

가장 높은탑쌓기

#include<bits/stdc++.h>
using namespace std;
struct Edge{
	int s, h, v;
	Edge(int a, int b, int c){
		s=a;
		h=b;
		v=c;
	}
	bool operator < (const Edge &e) const{
		return s>e.s;
	}
};
int main() {
	ios_base::sync_with_stdio(false);
	//freopen("input.txt", "rt", stdin);
	int n, j, res, v1, v2, v3;
	cin >> n;
	vector<Edge> a;
	vector<int> dy(n, 0);
	for(int i=0; i<n; i++){
		cin >> v1 >> v2 >> v3;
		a.push_back(Edge(v1, v2, v3));
	}
	sort(a.begin(), a.end());
	dy[0]=a[0].h;
	res=dy[0];
	for(int i=1; i<n; i++){
		int max=0;
		for(int j=0; j<=i-1; j++){
			if(a[i].v <a[j].v && dy[j]>max) max=dy[j];
		}
		dy[i]=max + a[i].h;
		if(res < dy[i]) res = dy[i];
		//cout << dy[i] << "\n";
	}
	cout<< res;
	return 0;
}

이 문제는 위로 갈수록 밑면이 점점 좁아지고 무게가 점점 가벼워져야 하는 조건을 만족 시켜야 한다.

 

부분증가수열과 최대 선 연결하기 문제는 숫자가 점점 증가하는 조건을 만족시키면서 가장 긴 수열을 택해야 하는문제로 본 문제와 맥락이 같다.

부분증가수열과 최대선연결하기 문제는 조건이 하나이나 이 문제는 밑면과 무게 이렇게 조건이 두개이다.

 

입력은 밑면, 높이, 무게 순으로 되어있으며 구조체를 통해서 입력받았다.

구조체를 통해 입력받은 후 sort함수를 통해 밑면이 큰 수부터 배치시킨다.

그 다음 무게가 그 전보다 작고 그 전에 쌓인 벽돌중 가장 높이가 높은  것을 골라 그 높이에 해당 인덱스의 높이를 더하면 된다.

 

높이를 더한 후 res에 저장하고 출력한다.