[Algorithm]Baekjoon 2655번 :: 가장높은탑쌓기

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
 
struct Node
{
    int index;
    int area;
    int height;
    int weight;
};
 
bool cmp(const Node& a, const Node& b)
{
    return a.area < b.area;
}
 
int n;
vector<Node> nodes;
int dp[101] = { 0 };
 
int DFS(int index, int sum)
{
    int& result = dp[index];
    if (result != -1) return result;
 
    result = 0;
 
    for (int i = index + 1; i <= n; ++i)
    {
        if (nodes[index].weight > nodes[i].weight) continue; 
 
        result = max(result, DFS(i, sum + nodes[i].height));
    }
 
    return result += nodes[index].height;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
    nodes.resize(n + 1);
    memset(dp, -1, sizeof(dp));
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> nodes[i].area >> nodes[i].height >> nodes[i].weight;
        nodes[i].index = i;
    }
 
    sort(nodes.begin(), nodes.end(), cmp);
    
    int height = DFS(0, 0);
    vector<int> result;
    int index = 1;
 
    while (index != n+1)
    {
        if (height == dp[index])
        {
            height -= nodes[index].height;
            result.push_back(nodes[index].index);
        }
        ++index;
    }
 
    cout << result.size() << endl;
 
    for (int i = 0; i < result.size(); ++i)
    {
        printf("%d\n", result[i]);
    }
}
 
 
 

 

 

조건에 맞춰서 벽돌을 쌓았을 때, 단순 최댓값을 구하는게 아니라 구성요소들을 구해야하는 문제이다.

그러나 구성요소를 구하기 위해 먼저 최댓값을 구해보자.

 

문제의 조건엔 면적도 따져야하고 무게도 따져야 한다. 

그러니 일단 면적이나 무게를 기준으로 정렬을 하자. 오름차순이든 내림차순이든 상관은 없다만, 보기편하게 오름차순을 했고 나같은경우 기준은 면적으로 했다. 즉 면적을 기준으로 오름차순정렬을 해줬다.

그리고 노드에 정보를 저장할 때 반드시 인덱스도 저장해줘야 한다.

정렬을 하기때문에 순서가 뒤죽박죽이 되니, 해당 노드가 어떤 인덱스였는지 미리 저장해놔야 한다.

정답으로 출력해야하는 인덱스는 처음 입력받은 순서여야하기 때문이다.

 

기준 한개는 오름차순정렬을 했으니 신경 안써도되고, 나머지 기준에 따라 최댓값dp테이블을 업데이트하면 된다.

이건 어렵지않으니... 굳이 설명은 안하겠다.

 

이후 최댓값에서 해당인덱스의 height값을 빼면서 역추적하면 된다.

나같은경우는 탑다운방식으로 DP테이블을 저장해서 DP[0]에 최댓값이 들어있다만, 바텀업방식으로 했다 가정하면 dp[n]에 최댓값이 들어있을 것이다.

그러면 최댓값 - n번쨰 인덱스에 해당하는 인덱스의 height값을 빼주면 나오는 값이 바로 이전 벽돌인덱스의 dp값이다.