백준 2805 나무 자르기

문제

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

2805번: 나무 자르기

틀린 내 코드

console.time("code_measure");

let fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";

const input = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");

const [[N, M], H] = input.map((v) => v.split(" ").map((x) => Number(x)));

H.sort((a, b) => a - b);

let avg = Math.floor(
  H.reduce((acc, cur) => {
    return (acc += cur);
  }, 0) / N
);

let result = 0;
let answer = 0;

while (result !== M) {
  result = binary(avg);
  if (result !== M) avg++;

  answer = avg;
}

function binary(avg) {
  let start = 0;
  let end = H.length - 1;
  let middle = Math.floor((start + end) / 2);

  let result = 0;
  while (start <= end) {
    const value = H[middle] - avg;

    if (H[middle] > M) {
      result += value;
      start = middle + 1;
    } else {
      end = middle - 1;
    }

    middle = Math.floor((start + end) / 2);
  }

  return result;
}

console.log(answer);

console.timeEnd("code_measure");

// 답 : 36
// code_measure: 4.187ms

틀린 로직

 

1. 먼저 배열의 모든 숫자를 평균을 내고

2. 그 평균 값을 배열의 값들에서 - 하고나서

3. 나머지 값들을 모두 더 했을 때 목표 값 20이 나오는지 검사하고

4. 아니면 아까 통계 낸 평균 값을 ++ 해주어서 목표 값에 도달하게 했습니다.

 

일단.. 테케 2개의 통과했으나 시간초과로 틀렸는데 다른 경우의 테케를 몇개 넣어보니 또 엉망이였습니다.

 

 

정답 로직

• 먼저 가장 작은 나무 배열의 0번째와 가장 큰 나무 배열의 마지막번째의 나누기 2를 해서 나무의 중간 크기를 낸다.
• 배열의 값들에 중간 크기 나무를 빼서 목표 길이가 나오면 통과

정답코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";

const input = require("fs")
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");

const [N, M] = input.shift().split(" ");
const trees = input[0]
  .split(" ")
  .map(Number)
  .sort((a, b) => a - b);

function solve(arr, target) {
  let start = 0; // 작은 나무
  let end = arr[arr.length - 1]; // 큰 나무

  while (start <= end) {
    let mid = Math.floor((start + end) / 2); // 중간 나무
    let sum = 0;

    for (let i = 0; i < arr.length; i++) {
      if (mid > arr[i]) {
        continue;
      }

      sum += arr[i] - mid;
    }

    if (sum >= target) {
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }
  return end;
}

console.log(solve(trees, M));