[백준][구현] 18111 마인크래프트 NodeJs 구현

목차

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

문제

 

문제 구현 방향

256 높이 부터 0 높이까지 줄여가며 최대 높이를 찾고 최대높이에서 하나씩 줄여가며 탐색해주는 식으로 진행하였다.

나중에 최적화를 한번 더 해보아야 할 것 같다...

 

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let [N, M, B] = input[0].trim().split(" ").map(Number);
let board = Array.from(Array(501), () => Array(501));
let dic = Array(258).fill(0);
let tms = 0;
let ans = [];
//사전에 추가
for (let i = 1; i < input.length; i++) {
  let ar = input[i].trim().split(" ").map(Number);
  for (let j = 0; j < ar.length; j++) {
    board[i - 1][j] = ar[j];
    dic[ar[j]]++;
  }
}

//가장 높은 높이 찾기
function mHigh() {
  let key = 0;
  for (let i = 256; i >= 0; i--) {
    if (dic[i] != 0) {
      key = i;
      break;
    }
  }
  return key;
}

//땅 파내고 인벤에 추가하기
function dig(high) {
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (high === board[i][j]) {
        board[i][j]--;
      }
    }
  }
  B += dic[high];
  if(high-1>=0)
    dic[high-1] += dic[high];
  tms += dic[high] * 2;
  dic[high] = 0;
}

//블럭 쌓아보기 인벤이 충분할경우에는 답 반환
function making(high) {
  let cnt = 0;
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      cnt += high - board[i][j];
    }
  }
  if (B >= cnt) return cnt;
  return 0;
}

//종료 조건 탐색하기
function counting() {
  let flag = 0;
  let a = board[0][0];
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (a == board[i][j]) flag++;
    }
  }
  return flag === N * M;
}


while (1) {
  let high = mHigh();
  if (counting()) {
    ans.push({ ts: tms, h: high });
    break;
  }
  let ts = making(high);
  if (ts) {
    ans.push({ ts: ts + tms, h: high });
  }
  dig(high);
}

//시간을 우선으로 정렬하고 그 후 높이순으로 정렬
ans.sort((a, b) => {
  if (a.ts != b.ts) {
    return a.ts - b.ts;
  } else {
    return b.h - a.h;
  }
});
console.log(ans[0].ts, ans[0].h);