#include "..\CookHeader.h"

int ROW = 5, COL = 5;
Array <Array <int>> goldMaze = { {1, 4, 4, 2, 2},
								 {1, 3, 3, 0, 5},
								 {1, 2, 4, 3, 0},
								 {3, 3, 0, 4, 2},
								 {1, 3, 4, 5, 3} };

void printMaze(Array <Array <int>> arr) {
	for (int i = 0; i < ROW; i++) {
		for (int k = 0; k < COL; k++) {
			printf("%3d ", arr[i][k]);
		}
		println("");
	}
}

int growRich() {
	Array <Array <int>> memo = emptyArray2(ROW, COL); // 5X5 빈 배열
	memo[0][0] = goldMaze[0][0];

	int rowSum = memo[0][0];
	for (int i = 1; i < ROW; i++) {
		rowSum += goldMaze[0][i];
		memo[0][i] = rowSum;
	}

	int colSum = memo[0][0];
	for (int i = 1; i < COL; i++) {
		colSum += goldMaze[i][0];
		memo[i][0] = colSum;
	}

	for (int row = 1; row < ROW; row++) {
		for (int col = 1; col < COL; col++) {
			if (memo[row][col - 1] > memo[row - 1][col])
				memo[row][col] = memo[row][col - 1] + goldMaze[row][col];
			else
				memo[row][col] = memo[row - 1][col] + goldMaze[row][col];
		}
	}

	int retValue = memo[ROW - 1][COL - 1];

	println("## 메모이제이션 ##");
	printMaze(memo);

	int row = ROW - 1;
	int col = COL - 1;
	memo[row][col] = 0;
	while (row != 0 || col != 0) {
		if (row - 1 >= 0 && col - 1 >= 0) {
			if (memo[row - 1][col] > memo[row][col - 1]) 
				row--;
			else 
				col--;
		}
		else if (row - 1 < 0 && col >= 0) 
			col--;
		else 
			row--;
		memo[row][col] = 0;
	}

	println("\n## 메모이제이션(황금 미로 길) ##");
	printMaze(memo);

	return retValue;
}

int main() {
	int macolGold = growRich();
	println("\n황금 미로에서 얻은 최대 황금 개수 -->" + to_string(macolGold));
}