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

https://www.acmicpc.net/problem/2655

2655번: 가장높은탑쌓기

 

[ 백준 2655번 가장높은탑쌓기 소스 코드 ]

#include <cstdio>
#include <algorithm>
using namespace std;
int z[110]={0,},p[110]={0,},max1=0,max2=0,b[110],o;
struct sung
{
	int n; //번호 
	int s; //넓이 
	int h; //높이
	int w; //무게 
}da[110];
void go(int x)
{
	if( x==0 ) return;
	go(p[x]);
	b[o] = da[x].n;
	o++;
}
int cmp(sung x,sung y)
{
	if( x.s<y.s ) return 1;
	else return 0;
}
int main()
{
	int i,j,m,t,x;
	scanf("%d", &m);
	for(i=1;i<=m;i++)
	{
		da[i].n = i;
		scanf("%d %d %d", &da[i].s,&da[i].h,&da[i].w);
	}
	sort(da,da+m+1,cmp);
	for(i=1;i<=m;i++)
	{
		t = 0;
		x = 0;
		for(j=1;j<i;j++)
		{
			if( da[i].w>da[j].w && t<z[j] )
			{
				t = z[j];
				x = j;
			}
		}
		z[i] = t + da[i].h;
		p[i] = x;
		if( max1<z[i] )
		{
			max1 = z[i];
			max2 = i;
		}
	}
	go(max2);
	printf("%d\n", o);
	for(i=0;i<o;i++) printf("%d\n", b[i]);
	return 0;
}