1072번: 게임

문제

형택이는 게임을 하면서 단 한 번도 진 적이 없습니다. 지금까지 진행한 게임의 횟수 X와 이긴 게임의 횟수 Y가 주어질 때, 승률 Z는 (Y / X) * 100의 소수점을 버린 정수값입니다. 앞으로 형택이가 하는 모든 게임에서 무조건 이긴다고 가정할 때, 승률 Z가 변하기 위해 최소 몇 판의 게임을 더 해야 하는지 구하는 문제입니다.

• 입력: 첫째 줄에 게임 횟수 X와 이긴 게임 횟수 Y가 주어집니다. (1 ≤ X ≤ 1,000,000,000, 0 ≤ Y ≤ X)
• 출력: 첫째 줄에 승률이 변하기 위해 더 해야 하는 최소 게임 횟수를 출력합니다. 만약 승률이 절대 변하지 않는다면 -1을 출력합니다.

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

풀이: 매개변수 탐색 (Parametric Search)

앞으로 추가로 진행해야 할 게임의 횟수(m)를 이분 탐색을 통해 찾아내는 방식입니다.

• 예외 처리 (기저 조건): 기존 승률 Z가 99 이상인 경우, 앞으로 아무리 게임을 많이 이겨도 승률이 100이 되거나 더 오를 수 없습니다(99.99...%는 버림 시 99%이므로 100%가 될 수 없음). 따라서 이 경우에는 즉시 -1을 출력하고 종료합니다.
• 이분 탐색 범위 설정: 추가로 진행할 게임 수의 최솟값을 s = 1로, 최댓값을 e = 1,000,000,000 (X의 최대 범위)으로 설정합니다.
• 승률 변화 판별: 중간값 m = (s + e) / 2판을 더 진행했다고 가정했을 때의 새로운 승률 100 * (y + m) / (x + m)을 계산합니다.
  1. 새로운 승률이 기존 Z보다 크다면: 승률을 변화시키는 데 성공했습니다. 더 적은 횟수로도 승률이 오르는지 확인하기 위해 탐색 상한선을 낮춥니다(e = m - 1). 동시에 현재의 m을 정답 후보(ans)로 저장합니다.
  2. 새로운 승률이 Z와 같다면: 아직 승률이 변하지 않았으므로, 게임을 더 많이 해야 합니다. 탐색 하한선을 높입니다(s = m + 1).
• 자료형 주의: 입력값의 범위가 10억까지이므로 계산 과정(100 * y 등)에서 정수 오버플로우가 발생하지 않도록 모든 변수를 long 타입으로 선언하여 계산합니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       StringTokenizer st = new StringTokenizer(br.readLine());
       long x = Integer.parseInt(st.nextToken());
       long y = Integer.parseInt(st.nextToken());
       long z = 100 * y / x;

       if (z >= 99) {
          bw.write("-1");
          bw.flush();
          return;
       }

       long s = 1;
       long e = 1000000000;
       long ans = -1;
       while (s <= e) {
          long m = (s + e) / 2;
          if (100 * (y + m) / (x + m) > z) {
             ans = m;
             e = m - 1;
          } else {
             s = m + 1;
          }
       }

       bw.write(ans + "");

       bw.flush();
    }
}

알고리즘 분류

수학 (Mathematics), 이분 탐색 (Binary Search)