백준 1654 랜선자르기 js

문제 링크

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

1654번: 랜선 자르기

 

정답코드

const fs = require("fs");

const filePath =
  process.platform === "linux" ? "/dev/stdin" : "./이분탐색/1654/input.txt";

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

const [n, k] = input
  .shift()
  .split(" ")
  .map((a) => +a);

const lines = input.map((a) => +a).sort((a, b) => a - b);

let max = Math.max(...lines);
let min = 1;

while (min <= max) {
  let mid = Math.floor((min + max) / 2);

  let line = lines
    .map((line) => Math.floor(line / mid))
    .reduce((acc, cur) => (acc += cur), 0);

  if (line >= k) {
    min = mid + 1;
  } else {
    max = mid - 1;
  }
}

console.log(max);

로직설명

• 가장 큰 값과 작은 값을 더하고 평균으로 mid 를 낸다. 
  • max 801 min 1 = 802 / 2 = mid =>401
• 배열의 값들을 평균 값으로 나눠서 모두 합하여 본다.
  • mid 가 401 일시 합산 값 == 5
• 합한 값이 5인데 목표 값 11이 되지 않았으니 max에 mid 401 -1 인 400 할당하고 다시 나누기 2를 한다.

이런식으로 값을 찾아낸다.

 

처음에 테케를 봤을 때 802 / 4 하면 200인데 이런식으로 하는게 맞나.. 아니면 나무자르기 처럼 값을 다 평균내야하나 생각하면서 이게 왜 이분탐색인지 모르겠었는데 딱 원하는 그 값을 찾는 이분탐색보다 좀 더 심화적으로 찾은 그 값에 근접한 값을 다시 탐색을 하는 이분탐색인거같다.