[백준 2655번] 가장높은탑쌓기 (C++)

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

1. 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.
2. 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다.
3. 벽돌들의 높이는 같을 수도 있다.
4. 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.
5. 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.

위의 조건을 만족하면서 가장 높게 탑을 쌓아야한다. 입력으로 주어지는 벽돌의 개수가 100개 이하이므로 모든 경우의 수를 다 훓어보기에 충분하다. 

훓을때 고려해야할 조건이 무게가 높은 블럭, 밑면적이 큰 블럭이 밑에 쌓여야만 한다.

본인은 밑면적 순으로 정렬해서 탐색할때 밑면적이 큰 놈이 밑으로 오게 하고 무게 조건은 if문으로 처리했다.

 

Dp[i]가 i개의 벽돌을 사용했을 때 가능한 가장 큰 높이가 아니다.

i번째 벽돌을 무조건 사용했을때 가능한 가장 큰 높이로 해야한다.

이유는 출력해야하는 값이 가장 높을때의 탑의 높이가 아니라 탑이 가장 높을때 몇번째 벽돌을 사용했는지를 출력해야하므로 벽돌에 id값을 붙여서 출력할때 써먹어야한다...출력을 위해 어떤 Dp로 수행할 건지 정해야하는 어려운문제...

 

정확하게 왜 dp를 i번째 벽돌을 무조건 사용했을때 가능한 가장 큰 높이로 해야하는지는 코드를 보고 출력을 위해 벽돌 번호를 어떻게 꺼냈는지 보면 이해할 수 있을 것이다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define endl "\n"
using namespace std;

struct Brick {
    int a, h, w, num;
};

bool compare(Brick x, Brick y){
    return x.a < y.a;
}

int main() {
    int n;
    cin >> n;
    vector<Brick> brick;
    Brick start = {0,0,0,0};
    brick.push_back(start);
    for(int i = 1; i <= n; i++){
        Brick b;
        cin >> b.a >> b.h >> b.w;
        b.num = i;
        brick.push_back(b);
    }
    sort(brick.begin(),brick.end(),compare);

    int dp[101], height = 0;
    memset(dp,0,sizeof(dp));
    
    //i번째 블록을 무조건 사용했을때 가능한 가장 높은 탑
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < i; j++){
            if(brick[i].w > brick[j].w){
                dp[i] = max(dp[i],dp[j]+brick[i].h);
            }
        }
        height = max(height,dp[i]);
    }
    vector<int> ans;
    for(int i = n; i > 0 ; i--){
        if(dp[i] == height){
            ans.push_back(brick[i].num);
            height -= brick[i].h;
        }
    }
    cout << ans.size() << endl;
    reverse(ans.begin(),ans.end());
    for(auto v : ans) cout << v << endl;
}