BOJ 2655 : 가장높은탑쌓기 [C++]

 

2655번: 가장높은탑쌓기

 

문제를 보고 생각난 풀이는 백트래킹, 추적할 수 있는 DP 두 가지였다.

하지만 벽돌의 수가 최대 100개이기 때문에 백트래킹으로 풀이할 경우 시간 초과가 날 것이라 제외했다.

 

문제 조건을 보면, 각 벽돌의 밑면 넓이와 무게는 모두 다르다.

나는 무게를 기준으로 삼아 내림차순으로 벽돌을 정렬했다.

 

DP 테이블을 만들어가며 추적까지 가능하도록 pair를 사용해서 테이블을 만들었다.

std::pair<int, int> dp[101];    // {total_height, from}

 

DP[i] : i번째 블록을 가장 위에 뒀을 때, 가능한 높이와 i번째 블록 아래에 오게 되는 블록의 위치를 나타낸다.

 

DP 테이블의 초기값은 각 벽돌 1개 만을 사용해서 만들어지는 {bricks[i].height, -1}로 초기화했다.

(from이 -1이라는 것은 탑의 가장 아래라는 뜻)

 

벽돌을 무게 기준으로 이미 정렬해 뒀기 때문에, DP 테이블을 만들 때 벽돌의 밑면 넓이만 고려하며 높이를 높여가면 된다.

 

DP 테이블을 완성한 후, 가장 높이가 높은 곳을 찾아 그곳부터 DP 테이블의 from을 타고 가며(탑의 위에서 아래로) 쌓인 벽돌의 번호를 구해준다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

struct brick {
    int index;
    int bottom;
    int height;
    int weight;
    brick() {};
    brick(int index, int bottom, int height, int weight) : index(index), bottom(bottom), height(height), weight(weight) {};
};

int N;
brick bricks[101];
std::pair<int, int> dp[101];    // {total_height, from}

int main() {
    std::cin >> N;

    int bottom = 0, height = 0, weight = 0;
    for (int i = 0; i < N; i++) {
        std::cin >> bottom >> height >> weight;
        bricks[i] = brick(i + 1, bottom, height, weight);
    }

    std::sort(bricks, bricks + N, [&](brick a, brick b) {
       return a.weight > b.weight;
    });

    for (int i = 0; i < N; i++) {
        dp[i] = {bricks[i].height, -1};
    }

    int maxHeight = 0, maxHeightsIndex = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            if (bricks[j].bottom <= bricks[i].bottom && dp[j].first < dp[i].first + bricks[j].height) {
                dp[j] = {dp[i].first + bricks[j].height, i};
            }
        }
    }
    for (int i = 0; i < N; i++) {
        if (dp[i].first > maxHeight) {
            maxHeight = dp[i].first;
            maxHeightsIndex = i;
        }
    }

    std::vector<int> trace;
    int index = maxHeightsIndex;
    while (index != -1) {
        trace.push_back(bricks[index].index);
        index = dp[index].second;
    }

    std::cout << trace.size() << "\n";
    for (auto i : trace) {
        std::cout << i << "\n";
    }

    return 0;
}