[Inflearn] 가장 높은 탑 쌓기(DP, LIS)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

(조건1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다. 

(조건2) 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다. 

(조건3) 벽돌들의 높이는 같을 수도 있다. 

(조건4) 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다. 

(조건5) 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다

조건 4, 5번이 가장 필요한 진또배기(?)이다.

쉽게 생각하면 넓이가 작고, 무게가 더 가벼운 벽돌을 쌓아 올리는 최대 부분 증가 수열이라고 생각하면 될 것이다.

#. Code

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
struct Blk {
    int area;
    int height;
    int weight;
 
    Blk(int a, int b, int c) {
        area = a;
        height = b;
        weight = c;
    }
    bool operator<(const Blk& b) const {
        return area > b.area;
    }
};
 
int main(void)
{
    int n, i, j, mx, a, b, c, res = 0;
    freopen("input.txt", "rt", stdin);
    scanf("%d", &n);
    vector<Blk> blocks;
    vector<int> dp(n);
 
    for (i = 0; i < n; i++) {
        scanf("%d %d %d", &a, &b, &c);
        blocks.push_back(Blk(a, b, c));
    }
 
    sort(blocks.begin(), blocks.end());
    dp[0] = blocks[0].height;
    res = dp[0];
    for (i = 1; i < n; i++) {
        mx = 0;
 
        for (j = i - 1; j >= 0; j--) {
            if (blocks[j].weight > blocks[i].weight && dp[j] > mx)
                mx = dp[j];
        }
 
        dp[i] = mx + blocks[i].height;
        if (res < dp[i])
            res = dp[i];
    }
 
    printf("%d\n", res);
 
    return 0;
}

line 34) 벽돌을 쌓기 위해서는 넓이 조건, 무게 조건을 따져야 하는데, 여기서 넓이 기준 내림차순으로 먼저 정렬을 해놓는다.

그러면 무게만 비교하면서 최대 높이를 구할 수 있다.

원래는 정렬을 안 하고, line 40에서 넓이랑 무게를 동시에 비교했었는데 계속 몇몇 testcase가 오답이 나와서

하나의 기준을 먼저 정렬한 후 다른 기준을 비교하였다.

* 정확하진 않을 수 있지만 내 생각으로는.. LIS를 적용하려면 하나의 조건만(?) 사용해야하는 듯 하다. 

  기본적인 수열에서 조건을 만족하는 최대 부분 증가 수열을 찾아가는 과정인데,

  두 가지 조건이 주어지게 되면, 최적의 해를 구할 수 없었다.

  그래서 두 가지 조건이 주어진다면 한 가지 조건은 기준을 잡고 정렬을 미리 해둔 후, 

  남은 조건을 사용하여 LIS를 적용해야할 것 같다.

line 35) 직관적인 작은 문제에 대한 해

line 37~48) 여기가 dp적용 코드이다.

line 40~43) 넓이 기준 내림차순으로 이미 정렬이 되어있으므로, 무게 기준으로만 비교해주면 된다.

    i번째 벽돌이 가장 위에 있다고 가정하였을 때, 자신보다 아래 있는 벽돌들을 확인하면서, 

    자신보다 무게가 크고, 가장 높이 쌓인 높이가 있다면 그 위에 벽돌을 쌓아줄 것이다.

#. Other code

#include<bits/stdc++.h>
using namespace std;
 
struct Brick{
    int s, h, w;
    Brick(int a, int b, int c){
        s=a, h=b, w=c;
    }
    bool operator<(const Brick &b)const{
        return s>b.s;
    }
};
 
int main(){
    ios_base::sync_with_stdio(false);
    int n, a, b, c, max_h=0, res=0;
    cin>>n;
    vector<Brick> Bricks;
    vector<int> dy(n, 0);
 
    for(int i=0; i<n; i++){
        cin>>a>>b>>c;
        Bricks.push_back(Brick(a, b, c));
    }
 
    sort(Bricks.begin(), Bricks.end());
    dy[0]=Bricks[0].h;
    res=dy[0];
 
    for(int i=1; i<n; i++){
        max_h=0;
        for(int j=i-1; j>=0; j--){
            if(Bricks[j].w > Bricks[i].w && dy[j]>max_h){
                max_h=dy[j];
            }
        }
        dy[i]=max_h+Bricks[i].h;
        res=max(res, dy[i]);
    }
 
    cout<<res;
    return 0;
}

#. Result

  - Input --------------------------------------------------------

5

25 3 4

4 4 6

9 2 3

16 2 5

1 5 2

------------------------------------------------------------------

  - Output --------------------------------------------------------

10

------------------------------------------------------------------