6. 가장 높은 탑 쌓기 질문

1강부터 쭉 들어왔지만 질문할만큼 막힌적이 없었는데... 이번에는 너무막혀.. 도움을 청해봅니다 ㅠㅠ

우선 강의 부분에서 가장 최대의 높이를 구하는 것을 해결할 수 있었습니다. 더 나아가 원 문제를 찾아보게 되었습니다. 원 문제를 질문하게 되어 먼저 죄송하다는 말씀 드리겠습니다...

원문제인 https://www.acmicpc.net/problem/2655 의 문제를 풀어보는데 너무 막히고 있습니다.

직접 구현한 코드는 다음과 같습니다.

cache배열의 원소를 pair로묶어, first에는 높이를, second에는 직전 block의 번호를 저장 시켰습니다.

이를 활용하여 출력하는 코드를구현하였는데, 분명 주어진 예시는 통과가 되는데 어디서 반례가 있는건지....

해결되지 않고있습니다 ㅠ.ㅠ 꼭좀 도와주시면 감사하겠습니다 ㅠ.ㅠ 

1) 첫 vt.push_back(Block(0, 0, 0)) 은 prt함수에서 0이 되었을때 탈출되는데, 배열을 0부터 채워넣으면 마지막값을 출력 못하는 문제가 발생하여 dummy 값으로 0번 배열을 채워준 후, 1번 배열부터 사용하고, 정렬하였습니다.

2) cnt 배열같은 경우 각 배열마다 몇개의 block을 사용하였는지를 저장하였습니다. 이를 통하여 차후 prt 함수를 호출할 때, 가장 높은 놈을 인자로 넘겨 출력하도록 하였습니다.

3) prt 함수는 넘겨받은 인자를 시작으로, vt[num].second 값들을 확인하면서 자신의 아래 block의 index 번호를 알아내어 해당 인덱스를 출력하여 재귀를 타고 내려가는 함수입니다.

index가 0이되면 return 하기때문에 이를 위해 앞에서 말했듯 dummy 값이 하나 맨아래층에 존재합니다.

4) main에서 cache배열의 출력은 디버깅 용 입니다. 답안을 백준에 제출할때는 제거후 제출했습니다.

#include <bits/stdc++.h>
using namespace std;
// https://www.acmicpc.net/problem/2655
#define rep(i,k) for(i = 0; i < k; i++)
#define REP(i,n,k) for(i = n; i < k; i++)

class Block{
public:
	int bottom, height, weight;
public:
	Block(int a, int b, int c) : bottom(a), height(b), weight(c) {};
	
	bool operator < (const Block& tmp) const {
		if(bottom != tmp.bottom) return bottom > tmp.bottom;
	}
};

vector<Block > vt;
int cnt[102];
vector<pair<int, int> > cache(102);

void prt(int num){
    if (num != 0) {
    	cout << num << "\n";
        prt(cache[num].second);
    }
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	freopen("input.txt", "rt", stdin);
	
	int num, i;
	
	cin >> num;

	vt.push_back(Block(0, 0, 0));
	REP(i, 1, num+1){
		int b, h, w;
		cin >> b >> h >> w;
		vt.push_back(Block(b, h, w));
	}
	
	sort(vt.begin()+1, vt.end());
	
	cnt[1] = 1;
 	cache[1].first = vt[1].height;
 	cache[1].second = 0;
 	
	for(i = 2; i <= num; i++){
		int res(0), indexcnt(0);
		for(int j = i-1; j > 0; j--){
			if(vt[j].weight > vt[i].weight && res < cache[j].first){
				res = cache[j].first;
				indexcnt =  j;
			}
		}
		cache[i].first = res+vt[i].height;
		cache[i].second = indexcnt;
		cnt[i] = cnt[indexcnt] + 1;
	}

	int maxcnt(-1);
	REP(i, 1, num+1){
		if(maxcnt < cnt[i]) maxcnt = cnt[i];
	}
	cout << maxcnt << "\n";
	
	cout << "cache : ";
	REP(i, 1, num+1){
		cout <<	cache[i].first << " ";
	}
	cout << "\n";
	
	int maxh(0), idx(0);
	REP(i, 1, num+1){
		if(maxh < cache[i].first) {
			maxh = cache[i].first;
			idx = i;
		}
	}
		
	prt(idx);
	

	return 0;
}

꼭 저의 방식이 아니더라도 사용한 벽돌을 백트레킹 할수 있는 방법을 알려주시면 감사하겠습니다 ㅠ.ㅠ