백준18111 - 마인크래프트 (완전탐색) node.js

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

 

문제 해결 방식

문제에서 중요한 힌트는 땅의 높낮이는 256 이하라는 것에서 착안해, 0부터 256까지의 자연수 x를 대입했을 때의 '걸리는 시간'을 모두 구하는 식으로 접근했다. (여기서, 박스의 갯수도 체크해야 하는데, 해당 자연수 x로 모든 땅을 고르게 만들 때의 박스가 부족한 경우는 Infinity 를 반환토록 하여 정답에서 배제하였다.)

이후, 256개의 원소를 담을 수 있는 공간에 해당 값들을 저장한 뒤, 가장 시간이 짧게 걸린 값을 찾았다. (이때, 최소 '걸리는 시간'이 같은 경우가 있을 때는, 가장 땅 높이가 높은 값을 추출해야 하므로, lastIndexOf 메서드를 활용하였다.)

 

전체 소스 코드

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

function solution(data) {
  const [[_, __, B], ...matrix] = data.map((el) => el.split(" ").map(Number));

  const arr = matrix.flat();

  function act(x) {
    let cnt = 0;
    let b = B;
    for (let i = 0; i < arr.length; i++) {
      const t = x - arr[i];
      if (t >= 0) {
        cnt += t;
        b -= t;
      } else {
        cnt -= 2 * t;
        b -= t;
      }
    }

    return 0 > b ? Infinity : cnt;
  }

  const storage = Array.from({ length: 257 }, () => 0);

  for (let i = 0; i <= 256; i++) {
    const time = act(i);
    storage[i] = time;
  }

  const min = Math.min(...storage);
  const result = storage.lastIndexOf(min);
  console.log(min, result);
}

solution(input);