문제

이해

형택이는 게임을 다시 시작한 이후에는 무조건 게임을 승리한다. 따라서, 형태이의 승률은 무조건 올라가게 되어 있는데 승률을 정수로 나타냈을때 승률이 변화하면 최소 게임 수를 구해야 한다.

예를 들어, 게임 횟수 X가 53, 승리 횟수 Y가 47 이라면 승률 Z는 88이다. (승률의 소수점 아래 자리는 버림)

이 상황에서 승률이 변화하는 게임 수를 구하면 된다. (위에서 설명했듯이 게임은 무조건 승리한다.)

접근

게임 수의 제한을 보면 1000000000 이하이다. 단순하게 생각했을 때 한판 한판 이겼을 때의 승률 변화를 체크할 수 있다. 승률이 올라갈때 반복문을 멈추고 그때의 판수가 정답이 된다.

하지만 게임 수는 최대 10억이므로 최악의 경우에는 10억의 승리횟수까지 반복문을 실행해야 한다. 이는 시간초과를 초래하기 때문에 다른 방법이 필요하다.

이 문제는 이분 탐색을 사용하기 좋다. 왜냐하면 게임 횟수는 1부터 1000000000으로 연속된 수열에서 탐색해야 하기 때문이다.

코드

package java_baekjoon;

import java.util.*;

public class prob1072_2 {
    static long x;
    static long y;
    static int target;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        x = sc.nextInt();
        y = sc.nextInt();

        target = (int) ((y * 100) / x);

        if (target >= 99) {
            System.out.println(-1);
            return;
        }

        int left = 0;
        int right = 1000000000;
        int result = -1;

        while (left <= right) {
            int mid = (left + right) / 2;
            int z = (int) (((y + mid) * 100) / (x + mid));

            if (target >= z) {
                result = mid + 1;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        System.out.println(result);
    }
}

반복문 내부를 보자. target은 원래의 승률이고 z는 mid에 따른 변화된 승률이다.

변경된 승률이 원래의 승률과 비교하여 같거나 작다면 mid보다 더 큰 범위에서 탐색할 필요가 있다. 따라서, left (최저)를 mid + 1로 설정한다. 여기서 result가 mid + 1이 되는 이유는 기존의 mid는 정답을 만족하지 않기 때문에 최소값으로 가능성이 있는 다음값인 +1로 저장하는 것이다. 이는 반복문을 수행하면서 계속 수정된다.

최후에는 left와 right가 같아지고 이때의 mid + 1이 게임의 최솟값이 된다.

    static void binary_search(int left, int right){
        int mid = (left + right)/2;

        if(left == right){
            ans = mid;
            return;
        }

        int z = (int) (((y + mid) * 100) / (x + mid));

        if(z <= target){
            binary_search(mid + 1, right);
        } else{
            binary_search(left, mid);
        }
    }

이분탐색은 재귀 함수로도 풀 수 있다. 쓰이는 알고리즘은 거의 같다.

결과