이진탐색

🥝 떡볶이 떡 만들기

입력

4 6
19 15 10 17

◼◼◼ Solution ◼◼◼

4. ...

문제 풀이

// Run by Node.js
const { count } = require("console");
const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let inputArr = [];
rl.on("line", function (line) {
  inputArr.push(line);
}).on("close", function () {
  solution();
  process.exit();
});

const solution = () => {
  let arr = [];
  for (let x of inputArr) {
    arr.push(x.split(" "));
  }
  for (let x of arr) {
    for (let i = 0; i < x.length; i++) {
      x[i] = parseInt(x[i]);
    }
  }
  let fL = arr[0];
  let tteokArr = arr[1];
  const M = fL[1];
  let lt = 0;
  let rt = Math.max(...tteokArr);
  let answer = 0;
  while (lt <= rt) {
    let mid = parseInt((lt + rt) / 2);
    let total = 0;
    for (let x of tteokArr) {
      if (x > mid) total += x - mid;
    }
    if (total === M) {
      answer = mid;
      break;
    } else if (total > M) lt = mid + 1;
    else rt = mid - 1;
  }
  console.log(answer);
};

구현할 때 개선점

x가 mid보다 클 때라고 조건을 명시하지 않아서 오류가 있었다. 예를 들어서 떡의 길이가 14이고 mid가 19라고 가정해보자. 문제에서 요구한바로는 이때 잘리는 떡의 길이는 0이 된다. 그런데 내 코드에서는 떡의 길이는 -5가 된다. 음수가 전체 떡의 길이 합에 포함되어 오류가 생겼다.
음수가 나오지 않도록 x가 mid보다 큰 경우에만 total에 합한다.
Before

    for (let x of tteokArr) {
      total += x - mid;
    }

After

    for (let x of tteokArr) {
      if (x > mid) total += x - mid;
    }

• 한 줄 평
  More Info: 벨로그 링크

---

🥝

입력

◼◼◼ Solution ◼◼◼

4. ...

문제 풀이

구현할 때 개선점

• 한 줄 평
  More Info: 벨로그 링크

---