[BOJ] 1072. 게임 (🥈, 이분 탐색/수학)

🔗

풀이

아래 2가지만 고려하면 쉽게 풀리는 이분탐색인데 둘 다 못해서 틀렸다.

1. 승률을 구할 때 소수점을 버리기 위해 곱해야 하는 100의 위치
2. -1이 나오는 경우

승률을 구하기 위해서는 X와 Y 자료형을 double 로 변경해서 구해야 하는데 이때 소수점 2자리까지만 구하고 나머지는 버리려면 100을 곱해야 한다. 보통 (Y/X) * 100 이렇게 구하게 되는데 이렇게 되면 X가 Y에 비해 너무 큰 경우 제대로 구해지지 않을 수 있다고? 한다. 아마 이미 0이 되어버려서 100을 곱해도 소용이 없나봄.. 그래서 Y 에 가깝게 100을 곱해야 제대로 구해진다.

두 번째는 아무리 승리를 해도 절대 이길 수 없는 경우인데 승률이 이미 99퍼 이상인 경우는 더 높은 게 100밖에 없는데 이미 승률이 99라는 건 몇 판 졌다는 거고 승률이 100이라는 건 단 한 번도 지지 않아야 나올 수 있는 승률이므로 99에서 100이 되는 건 불가능하다.

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

public class Main {
    static int transform(double X, double Y) {
        return (int) ((100 * Y / X));
    }
    
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        long X = sc.nextLong();
        long Y = sc.nextLong();

        int oddOfWinning = transform(X, Y);
        if (oddOfWinning >= 99) {
            System.out.println(-1);
        } else {
            long high = Long.MAX_VALUE;
            long low = 0;
    
            while (low <= high) {
                long mid = (low + high) / 2;
    
                if (transform(X + mid, Y + mid) > oddOfWinning) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
    
            System.out.println(low);
        }
    }
}