#include "..\CookHeader.h"

int ROW = 5, COL = 5;
Array <Array <int>> pinMaze = { {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} };

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

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

	int colSum = memo[0][0];
	for (int i = 1; i < COL; i++) {
		colSum += pinMaze[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] + pinMaze[row][col];
			else
				memo[row][col] = memo[row - 1][col] + pinMaze[row][col];
		}
	}

	return memo[ROW - 1][COL - 1];
}

int main() {
	int mininumPin = avoidPin();
	println("\n압정 미로에서 밟은 최소 압정 개수 -->" + to_string(mininumPin));
}