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

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

2655번: 가장높은탑쌓기

문제

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

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

입력

첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차례대로 양의 정수로 주어진다. 각 벽돌은 입력되는 순서대로 1부터 연속적인 번호를 가진다. 벽돌의 넓이, 높이 무게는 10,000보다 작거나 같은 자연수이다.

출력

탑을 쌓을 때 사용된 벽돌의 수를 빈칸없이 출력하고, 두 번째 줄부터는 탑의 가장 위 벽돌부터 가장 아래 벽돌까지 차례로 한 줄에 하나씩 벽돌 번호를 빈칸없이 출력한다.

---

풀이

문제에 대한 설명이 조금 부족해 헷갈리는 문제이다.

정리해서 얘기하자면

1. 입력값으로 벽돌의 정보들이 주어진다. 입력되는 순서가 벽돌의 번호이다.

2. 벽돌을 쌓을 때 무게 또는 넓이가 더 큰 벽돌을 더 작은 벽돌 위에 쌓을 수 없다.

3. 가장 높이 벽돌 탑을 쌓았을 때 벽돌의 개수와 위에서부터 벽돌의 번호를 출력한다.

 

문제를 이해하고 나면 DP(배낭 문제)로 쉽게 해결할 수 있을을 알 수 있다.

먼저 벽돌을 무게 또는 넓이로 내림차순으로 정렬한 뒤에

벽돌 순서대로 '해당 벽돌을 맨 밑에 쌓았을 때 최대 높이'를 저장하여 문제를 풀었다.

또한, 어떤 벽돌들이 사용되었는지 추적하기 위해 root배열에 부모 벽돌을 저장하였다.

예제 1의 DP 테이블은 다음과 같다.

높이가 10일 때가 최댓값이므로 5번째 벽돌의 번호, 5번째 벽돌의 부모인 3번째 벽돌의 번호, 3번째 벽돌의 부모인 1번 벽돌의 번호를 역으로 출력하면 된다. (해당 예제에서는 우연히도 5, 3, 1이다.)

코드

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

vector<vector<int>> bricks;
int dp[101];
int root[101];

int main(){
    int n;
    cin >> n;
    
    // 벡터의 인덱스 편의를 위해 더미값을 집어넣음
    bricks.push_back({0,0,0,0});
    for (int i = 1; i <= n; i++){
        int a, b, c;
        cin >> a >> b >> c;

        // 넓이, 무게, 높이, 번호 순으로 저장
        bricks.push_back({a, c, b, i});
    }

    sort(bricks.begin(), bricks.end());

    // 배낭 문제와 비슷하게 풀기
    for (int i = 1; i <= n; i++){
        // 벽돌 하나를 놓는게 높이가 가장 높은 경우
        dp[i] = bricks[i][2];
        root[i] = i;
        for (int j = 1; j < i; j++){
            // 무게, 넓이가 모두 크고 합친 게 기존보다 높은 경우
            if (bricks[j][1] < bricks[i][1]){
                if (dp[j]+bricks[i][2] > dp[i]){
                    dp[i] = dp[j]+bricks[i][2];
                    root[i] = j;
                }
            }
        }
    }
    
    // 역추적을 위해 마지막으로 추가한 벽돌을 찾음
    int lastBrick;
    int height = 0;
    for (int i = 1; i <= n; i++){
        if (dp[i] > height){
            height = dp[i];
            lastBrick = i;
        }
    }

    // 정답을 스택에 넣고 출력
    stack<int> answer;

    while (lastBrick != root[lastBrick]){
        answer.push(lastBrick);
        lastBrick = root[lastBrick];
    }
    answer.push(lastBrick);

    cout << answer.size() << "\n";
    while (!answer.empty()){
        cout << bricks[answer.top()][3] << "\n";
        answer.pop();
    }
    for (int i = 1; i <= n; i++){
        cout << dp[i] << " ";
    }
}