[BOJ/백준][Gold4] 2655 : 가장높은탑쌓기 (C++)

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

2655번: 가장높은탑쌓기

 

[난이도] Gold4
[유형] DP

[풀이]
구조체를 선언해서 index,넓이,높이,무게를 저장한 뒤 넓이의 내림차순으로 정렬한다.
그 뒤에 무게를 기준으로 LIS DP를 적용해서 최적의 케이스를 구해주면 된다.

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2655.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct P{
    int idx,width,height,weight;
};
int N,dp[101],par[101];
P a[101];
bool cmp(P& u,P& v){
    if(u.width > v.width) return 1;
    else if(u.width == v.width) return u.weight > v.weight;
    return 0;
}
int sol(int n){
    int& ret = dp[n];
    if(ret !=-1) return ret;
    ret = a[n].height;
    for(int i=n+1;i<=N;i++){
        if(a[n].weight > a[i].weight && ret < a[n].height+sol(i)) {
            ret = a[n].height+sol(i);
            par[n]=i;
        }
    }
    return ret;
}
void prt(int n,int cnt){
    if(n==0) {
        printf("%d\n",cnt);
        return;
    }
    prt(par[n],cnt+1);
    printf("%d\n",a[n].idx);
}
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++) {
        scanf("%d%d%d",&a[i].width,&a[i].height,&a[i].weight);
        a[i].idx=i;
    }
    sort(a+1,a+1+N,cmp);
    memset(dp,-1,sizeof(dp));
 
    a[0].weight=9e8;
    sol(0);
    prt(par[0],0);
}