BOJ 1072 - 게임

문제

BOJ 1072 - 게임

게임을 X번 하여 Y번 이겼다. 현재 승률 Z = floor(Y/X * 100)이다. 앞으로 게임을 계속 이겨서 승률이 변하려면 몇 번을 더 이겨야 하는지 구하는 문제이다. 승률이 절대 변할 수 없다면 -1을 출력한다.

입력

첫째 줄에 X와 Y가 주어진다. (1 ≤ Y < X ≤ 10^9)

출력

승률이 처음으로 변하는 게임 수를 출력한다. 변하지 않는다면 -1을 출력한다.

예제

입력:

10 8

출력:

1

입력:

100 99

출력:

-1

풀이

핵심 아이디어: 이분 탐색으로 getPercent(X+mid, Y+mid) != Z가 되는 최솟값 mid를 찾는다. 승률이 이미 99% 이상이면 절대 변하지 않으므로 -1이다.

단계별 풀이:

1. 현재 승률 Z = floor(Y * 100 / X)를 계산한다.
2. l=0, r=10^9로 이분 탐색 범위를 설정한다.
3. mid = (l+r)/2에 대해 getPercent(X+mid, Y+mid) != Z이면 ans = mid로 갱신하고 r = mid-1, 아니면 l = mid+1.
4. 탐색 종료 후 ans를 출력. 탐색이 실패하면 -1 출력.

주의사항: (long) y * 100 / x로 오버플로를 방지해야 한다. X, Y가 각각 최대 10^9이므로 y*100이 int 범위를 초과한다.

코드

package com.ssafy.an.day199;
 
import java.util.Scanner;
 
public class Day182BOJ1072승률이분탐색 { // 1072 승률 이분탐색
	static int X, Y, Z;
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		X = sc.nextInt();
		Y = sc.nextInt();
		Z = getPercent(X, Y);
 
		int ans = -1;
		int l = 0;
		int r = 1_000_000_000;
		while (l <= r) {
			int mid = (l + r) / 2;
 
			if (getPercent(X + mid, Y + mid) != Z) {
				ans = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		System.out.println(ans);
		sc.close();
	}
 
	static int getPercent(int x, int y) {
		return (int) ((long) y * 100 / x);
	}
}

복잡도

• 시간: O(log X) — 이분 탐색 범위가 최대 10^9
• 공간: O(1) — 상수 개의 변수만 사용