18111번 마인크래프트

문제 설명

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

18111번: 마인크래프트

문제 풀이 방법

이 문제는 기본적으로 완전탐색 알고리즘의 일종인 브루트포스 문제이다.

각 기준 높이에 맞는 시간과 최대 높이를 측정하여 정답을 도출한다.

 

블럭의 최대 높이는 256까지 이므로 반복문을 이용해 0부터 256까지의 기준 높이를 설정하며 각 블럭에서의 기준 높이까지 맞추기위해 필요한 제거 횟수와 채움 횟수를 측정, 제거한 블럭과 기존에 갖고있던 블럭의 수가 넣어야 하는 블럭의 개수보다 크거나 같은 경우에 총 소요 시간을 계산하여 기존의 시간과 비교후 최소의 시간과 최대의 블럭의 수를 넣어준다.

정답 코드

const input = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt')
  .toString().trim().split('\n')

const [N, M, B] = input.shift().split(' ').map(Number);
let arr = input.map(e => e.split(' ').map(Number));
let answer = [Infinity, -1];


for (let h = 0; h <= 256; h++){
  let removed = 0;
  let need = 0;
  for (let i = 0; i < N; i++){
    for (let j = 0; j < M; j++){
      const needBlock = arr[i][j] - h;
      if (needBlock < 0) need -= needBlock;
      else removed += needBlock;
    }
  }
  if (removed + B >= need) {
    const curTime = 2 * removed + need;
    if (curTime <= answer[0]) {
      answer = [curTime, h];
    }
  }
}

console.log(answer.join(' '));