게임

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

오늘의 학습 키워드

이진탐색

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다
• 시작점(left)와 끝점(right)을 기준으로 탐색 범위를 명시한다
• 각 단계마다 탐색 범위가 반으로 감소하므로, 로그(log) 복잡도를 가진다

대표적인 사례

• 매우 넓은(억 단위 이상) 탐색 범위에서 최적의 해를 찾아야 하는 경우
• 데이터를 정렬한 뒤에 다수의 쿼리(query)를 날려야 하는 경우

문제 해결 방법

• 승률은 이긴 게임(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);