[백준] 1072 게임 - javascript

📌 문제

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

📌 풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

let [x, y] = input[0].split(" ").map(Number);
let z = Math.floor( (100 * y / x));
let left = 1;
let right = 1000000000;
let ans = Infinity;
while (left <= right) {
  let mid = parseInt((left + right) / 2);
  let new_z = Math.floor( (100 * (y + mid) / (x + mid)));
  if (z !== new_z) {
    ans = Math.min(ans, mid);
    right = mid - 1;
  } else {
    left = mid + 1;
  }
}
if (ans === Infinity) console.log(-1);
else console.log(ans);

✔ 알고리즘 : 이분탐색

✔ 문제의 조건에서 앞으로의 모든게임에서 지지 않는다고 했으므로 새로운 확률을 계산할 때 분모와 분자에 각각 mid를 더해줘서 계산해야함

✔ 처음확률과 현재확률이 달라지는 순간 현재 ans보다 작으면 갱신하고 right를 줄여서 범위 확인

✔ 처음확률과 현재확률이 같다면 left를 늘려서 범위 확인

❗ 새로운 확률을 계산할 때

let new_z = Math.floor(((y + mid) / (x + mid)) * 100);

이렇게 계산하여 제출하였더니 틀렸습니다 가 떴다.

let new_z = Math.floor( (100 * (y + mid) / (x + mid)));

일단 이렇게 고쳐서 맞았습니다는 받았지만 두개가 무엇이 다른점이 있는지는 아직 잘 모르겠다...

✔ 난이도 : 백준 기준 실버3