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

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

#define BLOCK_MAX 101
using namespace std;

struct BlockInfo
{
	int index;
	int area;
	int height;
	int weight;
};

bool Sorted(BlockInfo &x, BlockInfo &y);

int main()
{
	ios::sync_with_stdio(false);

	
	int dp[BLOCK_MAX]{0};
	int n, max_height = 0;

	cin >> n;

	vector<BlockInfo> blocks(n + 1);
	vector<int> result;

	blocks[0] = { 0 };

	for (int i = 1; i <= n; i++)
	{
		cin >> blocks[i].area >> blocks[i].height >> blocks[i].weight;
		blocks[i].index = i;
	}

	sort(blocks.begin(), blocks.end(), Sorted);

	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			//비교할 블록이 현재 블록보다 너비가 작을때
			if (blocks[j].area < blocks[i].area)
				dp[i] = max(dp[i], dp[j] + blocks[i].height);
		}
		max_height = max(max_height, dp[i]); //제일 높은 높이와 그 인덱스
	}

	while(n)
	{
		if (max_height == dp[n])	//현재 최대 높이와 같다면
		{
			result.push_back(blocks[n].index);	//번호를 추출
			max_height -= blocks[n].height;	//해당 높이를 가진 인덱스의 높이를 최대높이에서 감소
		}
		n--;
	}

	cout << result.size() << "\n";	//블록의 쌓은 개수

	for(int i = result.size() - 1; i >= 0; i--)
	{
		cout << result[i] << "\n";
	}

}

bool Sorted(BlockInfo &x, BlockInfo &y)
{
	return x.weight < y.weight;
}

 

해결 방안

1. 블록의 정보를 받아온다. (받아오는 순서대로 번호를 매겨야 됨.)
2. 블록의 무게별로 정렬을 한다.
3. 메모이제이션으로 하나씩 값을 저장한다.
   - 비교할 블록이 현재 지정한 블록보다 작을 경우.
   - i번째의 높이를 더한 최대 값을 넣을 dp[i]와 현재 높이 dp[j]에 i번째의 높이를 더한 값을 비교하여 최대 높이를 넣는다.
4. 최대 높이에서 인덱스를 추출후 해당 높이를 빼고 그 높이에서 인덱스를 추출하고를 반복한다.

 

순서도 및 풀이

dp[1] = 5

dp[2] = 2 7

dp[3] = 3 8 10

dp[4] = 2 7 9 9

dp[5] = 4 9 9 9 9

순으로 값이 저장된다. 최종 값이 그 자리를 제일 밑 블록으로 한 최고 높이가 된다.

 

10부터

10 - 3

7 - 2

5 - 5

0

 

10은 인덱스 3이니 block[3]의 index는 1

7은 인덱스 2이니 block[2]의 index는 3

5는 인덱스 1이니 block[1]의 index는 5

 

가장 꼭대기의 값 부터 불러오기 때문에

5

3

1이 된다.