마인크래프트

문제

언어

  • JavaScript

순서도

  1. 주어진 땅의 모든 블록의 높이가 0 ~ 256 이 될 때까지 각 블록의 높이를 변경하는 과정을 반복
  2. 반복을 진행하며 소요 시간이 최소인 경우의 시간과 높이를 기록
  3. 소요 시간이 같다면 높이가 가장 높은 경우를 출력

문제 풀이 step 1

  • 브루트 포스 방식의 문제로 가능한 모든 경우를 만들어보고, 그 중에서 최적의 답을 찾는 문제입니다.
  • N x M 크기의 땅이 있습니다.
  • 그 땅 위에 집을 짓기 위해서 ‘땅 고르기’ 작업을 하려고 합니다.
  • ‘땅 고르기’ 작업은 두 가지 방법을 이용합니다.
    1. 좌표 (i, j) 의 가장 위에 있는 블록을 제거하여 인벤토리에 넣습니다. (소요시간 : 2초)
    2. 인벤토리에서 블록 하나를 꺼내어 좌표 (i, j) 의 가장 위에 있는 블록 위에 놓습니다. (소요시간 : 1초)
  • ‘땅 고르기’ 작업에 걸리는 최소 시간과 그 경우 땅의 높이를 출력하는 문제입니다.
    • 이 때, 최소 시간이 동일하다면 땅의 높이가 가장 높은 경우를 출력해야 합니다.

문제 풀이 step 2

  • 브루트 포스 방식을 쓰기 위해서는 모든 경우가 과연 시간 내에 가능한 지를 확인해야 합니다.
  • 본 문제에서 땅의 최대 너비은 500 x 500 으로 250000 이고, 가능한 모든 높이의 경우는 0 ~ 256 으로 257 입니다.
  • 따라서 모든 경우는 64250000 이고, 충분히 시간 내에 할 수 있습니다.

문제 풀이 step 3

  • 주어진 땅의 각 블록의 높이를 0, 1, 2, …, 256 으로 만들어가며 그 때의 소요 시간과 높이를 기록합니다.
    • 그리고 인벤토리에 있는 블록의 수가 주어지는데, 그 수를 넘어갈 정도로 사용하면 안됩니다.
    • 즉, 인벤토리에 있는 블록의 수를 다 썼는데, 블록이 더 필요하다면 그 높이는 만들 수 없는 경우입니다.
  • 그리고 소요 시간이 같다면, 가장 큰 높이를 만들 수 있는 경우의 소요 시간과 땅의 높이를 출력합니다.
  • 추가 설명은 주석으로 작성하겠습니다.

소스 코드 1

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const [n, m, b] = input[0].split(" ").map(Number);
	const land = input.slice(1, n + 1).map((v) => v.split(" ").map(Number));

	let min = Number.MAX_SAFE_INTEGER;
	let height = null;
	for (let i = 0; i <= 256; i++) {
		// 인벤토리 초기화
		let inventory = b;
		let sum = 0;

		for (let j = 0; j < n; j++) {
			for (let k = 0; k < m; k++) {
				// 땅의 블록의 높이가 만드려는 높이 (i) 와 같다면, 손댈 필요 없음
				if (i === land[j][k]) continue;

				if (i < land[j][k]) {
					// 땅의 블록의 높이가 만드려는 높이 (i) 보다 크다면,
					// 2 초씩 소모하며 땅의 블록을 제거해서 인벤토리에 넣기
					let diff = land[j][k] - i;
					inventory += diff;
					sum += diff * 2;
				} else {
					// 땅의 블록의 높이가 만드려는 높이 (i) 보다 작다면,
					// 1 초씩 소모하며 인벤토리에서 블록을 꺼내서 땅의 블록에 추가하기
					let diff = i - land[j][k];
					inventory -= diff;
					sum += diff;
				}
			}
		}

		// 인벤토리에 있는 블록보다 더 사용했다면, 만드려는 높이 (i) 는 만들 수 없음
		if (inventory < 0) continue;

		// 최소 소요 시간을 갱신하고, 그 때의 높이를 기록
		if (min > sum) {
			min = sum;
			height = i;
		}

		// 최소 소요 시간이 같다면, 높이가 더 높은 경우로 갱신
		if (min === sum) {
			height = Math.max(height, i);
		}
	}

	return `${min} ${height}`;
};

console.log(solution(input));