Winter2017@Study 과제2 #가장높은탑쌓기 - 김영준

드디어 가장높은 탑을 쌓았다. 매우어려웠다. 배고프고 졸리고 머리아프다. 하하

과제 02 - 2655번 : 가장높은탑쌓기

#include< iostream >
using namespace std;

//벽돌 구조체 선언
struct Brick {
	int index, area, height, weight;
};

Brick br[101] = {};
int H[101] = {}; //높이 메모이제이션을 위한 배열
int A[101] = {}; //바로 위 벽돌 저장 배열
int Count[101] = {}; //각 인덱스 별로 최대로 쌓을 수 있는 벽돌의 개수

//무게를 기준으로 오름차순 정렬
void sort(Brick* arr, int n) {
	Brick temp;
	for (int i = 1; i < n - 1; i++) {
		for (int j = 1; j < n - 1; j++) {
			if (arr[j].weight > arr[j + 1].weight) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

//출력 함수
//재귀 이용, 바로 위 벽돌 인덱스 접근.
void Print(int n) {
	if (n != 0) {
		Print(A[n]);
		cout << br[n].index << endl;
	}
}

int main() {

	int n;
	int max_height = 0, max_index = 0;
	cin >> n;

	for (int i = 1; i <= n; i++) {
		br[i].index = i;
		cin >> br[i].area >> br[i].height >> br[i].weight;
	}
	
	sort(br, n+1); //무게 중심으로 정렬

	//알고리즘
	for (int i = 1; i <= n; i++) {
		for (int j = i - 1; j >= 0; j--) {
			//넓이 비교 : 오름차순 정렬이 되어있을 때
			//아래 벽돌과 위 벽돌을 비교 했을 때 아래 벽돌의 면적이 더 큰 경우 실행
			if (br[i].area > br[j].area) {
				//i번째 인덱스 벽돌을 제일 하단 벽돌이라 생각할 경우,
				//H[i]는 그 인덱스를 최하단 벽돌로 둘 경우 최대 높이.
				//j번째 벽돌이 조건에 만족하고,
				//j번째 벽돌을 최하단 벽돌이라 했을때 최대 높이를 더했을 때 H[i] 보다 높아질경우 실행
				if (H[i] < H[j] + br[i].height) {
					H[i] = H[j] + br[i].height;
					A[i] = j; //해당 인덱스 벽돌을 최하단 벽돌로 했을 때 바로 위 벽돌 인덱스.
					Count[i] = Count[j] + 1; //해당 인덱스의 벽돌을 최하단 벽돌로 했을 때의 개수.
				}
			}
		}
		//최대 높이, 최하단 벽돌 인덱스 갱신
		if (H[i] > max_height) {
			max_height = H[i];
			max_index = i;
		}
	}
	
	//출력
	cout << Count[max_index] << endl;
	Print(max_index);

	return 0;
}

이 문제는 알고리즘 구상은 쉬웠지만 구현이 어려웠다. 답 출력을 위한 알고리즘을 생각해내는데가 제일 힘들었다.

1) 무게를 기준으로 벽돌을 오름차순 정렬.

2) 면적을 기준으로 비교

3) 조건을 만족할 경우, i인덱스의 벽돌을 최하단 벽돌로 했을 때의 최대 높이를 메모이제이션.

4) 조건을 만족할 때, 갯수와 i인덱스 벽돌 바로 위 인덱스 저장.

5) 정답 출력.

스튜디오에서 예제가 맞게 출력되길래 채점했더니 바로 정답이었다. 신기한 경험이었다.

내일 10시부터 근로인데 망한 것 같다... 

'과제 03 -  1146번 : 지그재그서기' 는 다음에 풀어야겠다. 참 재밌는 문제풀이 시간이었다^^.