[백준] 18111 마인크래프트 - javascript

📌 문제

https://www.acmicpc.net/problem/18111

📌 풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const [n, m, b] = input.shift().split(" ").map(Number);
const arr = input.map(i => i.split(" ").map(Number));

let ansTime = Infinity;
let ansHeight = -1;

for (let h = 0; h <= 256; h++) {
  let inventory = 0;
  let removeCnt = 0;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      let curh = arr[i][j] - h;
      if (curh < 0) inventory -= curh;
      else removeCnt += curh;
    }
  }

  if (removeCnt + b >= inventory) {
    let time = 2 * removeCnt + inventory;
    if (ansTime >= time) {
      ansTime = time;
      ansHeight = h;
    }
  }
}

console.log(ansTime, ansHeight);

✔ 알고리즘 : 구현 (브루트포스)

✔ 높이를 0부터 문제조건에 있는 256까지 모두 탐색을 하며 가능한 여부인지 확인해야하는 브루트포스 문제이다

✔ 3중 for문으로 첫번째 for문은 설정할 높이 두번째 for문과 세번째 for문으로 arr를 탐색한다.

✔ 현재칸의 높이에서 현재 설정한 높이(h)를 뺀 값이 음수인 경우

if (curh < 0) inventory -= curh;

👉 더 높은 높이로 만들어야 한다. 따라서 inventory에 추가해준다 (curh가 음수이기 때문에 -=연산자를 사용해야 inventory값은 양수가 된다.)

✔ 현재칸의 높이에서 현재 설정한 높이(h)를 뺀 값이 양수인 경우

 else removeCnt += curh;

👉 더 낮은 높이로 만들어야 한다. 따라서 블록을 제거해야 하므로 removeCnt를 차이(curh)만큼 더해준다.

✔ 제거한 블록인 removeCnt와 원래 가지고 있던 블록인 b의 합이 추가를 해야하는 연산수인 inventory 값 보다 크거나 같으면 만들 수 있는 경우이다. 대소비교하여 값을 갱신해준다.

✔ 난이도 : 백준 기준 실버 2