백준 2655번 가장 높은 탑 쌓기

백준 2655번 - 가장 높은 탑 쌓기

가장 높은 탑 쌓기 문제의 경우 전형적인 dp문제 중 하나이다. 조건 중 하나가 밑의 블럭의 크기와 무게가 현재 블럭 보다 더 커야 한다는 조건이 있다. 이전의 위치한 블럭의 값 들과 계속해서 비교하면서 값을 업데이트해준다.

 

우선 시작하기전에 필자의 경우에는 넓이의 기준으로 내림차순으로 정렬했다. (물론 무게를 기준으로 정렬해도 된다.) 그래서 블럭의 이전의 값들과 비교하기 편하다. 내림차순이면 이전의 넓이는 항상 큰 값이 된다.

 

따라서 점화식은 아래와 같다.  dp[i] i번째 블럭의 가장 높은 높이이다.

if(올릴 수 있는 블럭이라면) { // 현재 블럭이 더 가볍고 부피가 작다면
	dp[now] = max(dp[now], dp[prev] + height[now]);
}

 

문제가 가장 높은 높이를 구하는 문제였으면 dp값 중 가장 큰 값을 출력하면 되지만 이 문제의 경우 가장 큰 값을 찾아가는 tracking이 필요했다. 그래서 Dp에 이전의 인덱스를 저장해서 해결해주었다. 

 

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

vector<pair<int, int> > dp(103);
vector<pair<int, pair<int, int> > > sub;
vector<pair<int, pair<int, int> > > order;
vector<int> result;

void solve();
bool isCorrectBox(int prev, int now);

int N;
int main(){	
	int area, height, weight;
	scanf("%d", &N);
	for(int i = 0; i < N; i++){
		scanf("%d %d %d", &area, &height, &weight);
		sub.push_back(make_pair(area, make_pair(height, weight)));
		order.push_back(make_pair(area, make_pair(height, i)));
	}

	sort(sub.begin(), sub.end(), greater<pair<int, pair<int, int> > >());
	sort(order.begin(), order.end(), greater<pair<int, pair<int, int> > >());
	solve();
}

void solve(){
	dp[0].first = sub[0].second.first;
	dp[0].second = 0;


	for(int now = 1; now < N; now++){
		dp[now].first = sub[now].second.first;
		for(int prev = 0; prev < now; prev++){
			if(isCorrectBox(prev, now)){
				if(dp[now].first < dp[prev].first + sub[now].second.first){
					dp[now].first = dp[prev].first + sub[now].second.first;
					dp[now].second = prev;
				}
			}
		}
	}

	// dp 코드

	int maxValue = 0, maxIndex;

	for(int i = 0; i < N; i++){
		if(maxValue < dp[i].first){
			maxValue = dp[i].first;
			maxIndex = i;
		}
	}

	int compareNum = 0;

	while(maxValue !=  compareNum){
		result.push_back(order[maxIndex].second.second);
		compareNum +=order[maxIndex].second.first;
		maxIndex = dp[maxIndex].second;
	}

	printf("%d\n", result.size());

	for(auto rank : result){
		printf("%d\n", rank+1);
	}
}


bool isCorrectBox(int prev, int now){
	if(sub[now].first < sub[prev].first && sub[now].second.second < sub[prev].second.second)
		return true;
	return false;
}