[BOJ / 백준] 18111번 마인크래프트 ( Node js / Javascript )

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

18111번: 마인크래프트

 

 

 

문제 풀이

 

위 문제의 주제는 최소한의 작업 시간으로 땅을 평탄화시키는 것이고,

 

이를 잘 생각해보면 최소한의 작업 시간으로 땅을 평탄화를 시켰을 때 나올 땅의 높이를 구하면 된다는 것을 알 수 있다.

 

마침 땅의 높이도 ( 0 <= H <= 256 )으로 상당히 작은 범위에 국한되어 있기 때문에 이를 주체로 반복문을 돌려보아도 전혀 부담이 없을 것이다.

 

결국엔 목표 높이를 0 ~ 256 사이의 수로 설정한 뒤, 모든 좌표를 돌며 땅의 높이를 목표 높이로 만들기 위해 얼만큼의 작업시간이 소요되는지를 구하고,

 

이를 전부 더한 전체 소요시간을 반복문을 거쳐 가장 적은 전체 소요시간과 해당 높이를 남기면 된다.

 

본인은 블록을 파내면 인벤토리에 블록이 채워진다는 점을 간과하여 문제 난이도에 비해 많이 헤맸다.

 

const fs = require("fs");

let input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((item) => item.split(" ").map((item) => Number(item)));

let [N, M, B] = input.shift();

let blocks = [].concat(...input);
let min_height = Math.min(...blocks);
let inventory = B;
let bestTime = Infinity;
let bestHeight = 0;

for (let H = min_height; H <= 256; H++) {
  let currentTime = 0;
  let currentInventory = inventory;

  for (let i = 0; i < blocks.length; i++) {
    if (blocks[i] < H) {
      currentTime += H - blocks[i]; // 블록 추가
      currentInventory -= H - blocks[i];
    } else if (blocks[i] > H) {
      currentTime += 2 * (blocks[i] - H); // 블록 제거
      currentInventory += blocks[i] - H;
    }
  }

  if (
    currentInventory >= 0 &&
    (currentTime < bestTime || (currentTime === bestTime && H > bestHeight))
  ) {
    bestTime = currentTime;
    bestHeight = H;
  }
}

console.log(`${bestTime} ${bestHeight}`);