[알고리즘] 마인크래프트

구현 방식

• 높이가 h 인 땅을 만들기 위해 걸리는 시간을 구했을 때, 최소 시간이 걸리는 높이를 구한다.
• 이때 높이는 배치된 땅 중 최소 높이 ~ 배치된 땅 중 최대 높이 의 사이값일 것이다.
  • 최소 높이보다 더 파거나 최대 높이보다 더 쌓으면 초과해서 일하는 것이기 때문,
• 하지만, 현재 갖고 있는 총 블록 수로 쌓을 수 있어야하므로 쌓을 수 있는 최대 높이는 아래와 같다.

쌓을 수 있는 최대 높이 = min(배치된 땅 중 최대 높이, 총 블록수 / (땅 면적))

• 즉, 구한 높이 사이값 중에서 최소 시간이 걸리는 높이를 구하면 되는 것이다!

코드

• 최종 코드는 아래와 같다.

const int MAXSIZE = 500;
int board[MAXSIZE][MAXSIZE] = {};

void solution(int N, int M, int inventoryBlocks)
{
	// 최소 시간 , 최소 시간중 최대 높이
	int resultTime = INT_MAX, resultHeight = INT_MIN;
	int totalBlocks, minHeight, maxHeight;
	calcBlockCount(N, M, inventoryBlocks, totalBlocks, minHeight, maxHeight);
	maxHeight = min(maxHeight, totalBlocks / (N * M));

	for (int h = minHeight; h <= maxHeight; h++)
	{
		int t = getBuildTime(N, M, h);
		if (t < resultTime)
		{
			resultTime = t;
			resultHeight = h;
		}
		else if (t == resultTime) resultHeight = max(resultHeight, h);
	}

	cout << resultTime << " " << resultHeight;
}

void calcBlockCount(int N, int M,int inventoryBlocks, int& totalBlocks, int& minHeight, int& maxHeight)
{
	totalBlocks = inventoryBlocks;
	minHeight = INT_MAX;
	maxHeight = INT_MIN;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			totalBlocks += board[i][j];
			minHeight = min(board[i][j], minHeight);
			maxHeight = max(board[i][j], maxHeight);
		}
}

int getBuildTime(int N, int M, int targetHeight)
{
	int t = 0;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			if (targetHeight == board[i][j]) continue;
			else if (targetHeight < board[i][j]) t += (board[i][j] - targetHeight) * 2;
			else t += (targetHeight - board[i][j]);
		}

	return t;
}