게임 (opens in a new tab)

문제 해결 방법

승률은 이긴 게임(Y) * 100 / 게임횟수(X)에서 소숫점을 버린 값이다
승률이 절대 변하지 않을 경우, -1을 출력한다
게임 횟수는 1 이상 1,000,000,000 이하이다 => 이진 탐색의 l(left) 값을 1, r(right) 값을 1,000,000,000으로 설정한다

오답노트

시간 복잡도를 개선했는지
- 처음에는 이진탐색을 이용하지 않고, while문을 돌며 승률이 변할 때까지 cnt 값을 증가시켰다
- 이 방법은 게임 횟수가 많지 않은 경우에는 문제가 없지만, 숫자가 커질수록 효율성이 떨어졌다 (시간복잡도 이슈)

코드

const fs = require("fs");
const filePath = process.platform == "linux" ? "/dev/stdin" : "./input.txt";
let [X, Y] = fs.readFileSync(filePath).toString().trim().split(" ").map(Number);
 
const checkWinRate = (total, winCnt) => Math.floor((winCnt * 100) / total);
 
const Z = checkWinRate(X, Y);
 
let l = 1;
let r = 1000000000;
let cnt = Infinity;
 
while (l <= r) {
  let mid = parseInt((l + r) / 2);
  let newZ = checkWinRate(X + mid, Y + mid);
 
  if (Z !== newZ) {
    cnt = Math.min(cnt, mid);
    r = mid - 1;
  } else {
    l = mid + 1;
  }
}
 
cnt === Infinity ? console.log(-1) : console.log(cnt);

24444 11561