[알고리즘 C++] 백준 2655 - 가장높은탑쌓기

#include <bits/stdc++.h>

using namespace std;

int N;
/* width, weight, height, idx */
tuple<int, int, int, int> blocks[101];

int dp[101];
int last[101];


int main(void)
{
    cin >> N;

    for (int n = 1; n <= N; n++)
    {
        int width, height, weight;
        cin >> width >> height >> weight;

        blocks[n] = make_tuple(width, weight, height, n);
    }

    /* 내림차순으로 */
    sort(&blocks[1], &blocks[N+1], greater<tuple<int, int, int, int>>());

#if 0
    for (int n = 1; n <= N; n++)
    {
        printf("width %2d weight %2d height %2d idx %d\n",
                get<0>(blocks[n]),
                get<1>(blocks[n]),
                get<2>(blocks[n]),
                get<3>(blocks[n]));
    }
#endif

    /* 기저조건 */
    dp[0] = 0;
    dp[1] = get<2>(blocks[1]);

    for (int i = 2; i <= N; i++)
    {
        int mxidx = 0;
        int mx = 0;

        for (int j = 1; j < i; j++)
        {
            if (get<0>(blocks[j]) < get<0>(blocks[i]) ||
                get<1>(blocks[j]) < get<1>(blocks[i]))
                continue;

            if (dp[j] > mx)
            {
                mx = dp[j];
                mxidx = j;
            }
        }

        dp[i] = mx + get<2>(blocks[i]);
        last[i] = mxidx;
    }

#if 0
    for (int n = 1; n <= N; n++)
    {
        printf("%2d ", dp[n]);
    }
    printf("\n");
#endif

    /* 가장 높은 높이를 만들수 있는 꼭대기 블록을 찾는다. */
    int mx = INT_MIN;
    int mxidx;

    for (int i = 1; i <= N; i++)
    {
        if (dp[i] > mx)
        {
            mx = dp[i];
            mxidx = i;
        }
    }

    /* 답을 역추적해 나간다 */
    list<int> ans;
    while (mxidx)
    {
        ans.push_back(get<3>(blocks[mxidx]));
        mxidx = last[mxidx];
    }

    cout << ans.size() << "\n";

    for (int v: ans)
        cout << v << "\n";

    return 0;
}