알고리즘 :: 백준 :: DP :: 2655 :: 가장높은탑쌓기

문제

밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프로그램을 작성하시오.

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

문제접근

1. 답과 밀접하게 관련있는 주 변위는 높이이지만 비교해야 하는 변위는 넓이와 무게이므로 변수가 많아서 어렵게 느껴지는 문제다.
2. 답에 영향을 주는 변수가 많은 경우 우리가 활용할 수 있는 가장 좋은 무기는 정렬과 변수 고정이다.
3. 이 문제의 핵심은 무게또는 넓이 중 어느 한 변수에 대해 정렬시킨 뒤 다른 변수를 통해 조건 세우는 것이다.
4. 본 코드에서는 무게에 대해 정렬시킨 뒤 넓이에 대해 조건을 세웠다.
   우리가 메모할 사항은 i번째 벽돌을 맨 아래에 놨을 때 세울 수 있는 최대 높이이다.

코드

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

typedef struct Stat {
    int area, height, weight, index;
}Stat;

int n;
int dp[101], arr[101], counts[101];
vector<Stat> vec(101);

void print(int n) {
    if (n != 0) {
        print(arr[n]);
        cout << vec[n].index << '\n';
    }
}
void q2655() {
    int maxHeight = 0, maxIdx = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = i - 1; j >= 0; --j) {
            if (vec[i].area > vec[j].area) {
                // 만일 현재 기록된 높이보다 더 높은 탑을 쌓을 수 있다면 갱신해준다.
                if (dp[i] < dp[j] + vec[i].height) {
                    dp[i] = dp[j] + vec[i].height;  // 해당 높이를 기록한다.
                    arr[i] = j;                     // i번째 위에 j번 탑이 있음.
                    counts[i] = counts[j] + 1;      // i번째가 제일 밑에 있을 때 쌓을 수 있는 개수
                }
            }
        }
        if (maxHeight < dp[i]) {    // 최대 높이를 갱신할 수 있다면 갱신한다.
            maxHeight = dp[i];
            maxIdx = i;
        }
    }
    cout << counts[maxIdx] << '\n';
    print(maxIdx);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> vec[i].area >> vec[i].height >> vec[i].weight;
        vec[i].index = i;
    }
    sort(begin(vec) + 1, begin(vec) + n + 1, [](const Stat& lhs, const Stat& rhs) {
        return (lhs.weight < rhs.weight);
    });	// 무게에 대해 오름차순 정렬한다. 
    q2655();
}

결과