[JAVA/Binary Search] 백준 1072 게임

1. 문제

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

1072번: 게임

 

2. 풀이

이진탐색을 사용한다. 새롭게 해야 하는 게임의 수를 이진탐색을 사용해서 찾는다.

소숫점을 버리기 위해 새로한 게임을 포함한 승률을 구하는 가정에서 100을 곱하게 되는데, 이 때 int 범위의 수가 넘을 수 있으므로 long 처리를 해줘야 된다는 것을 주의 해야 한다.

 

3. 코드

 

import java.util.Scanner;

//이진탐색

public class Main_1072 {
    
    public static int getScore(int x, int y) {
        return (int)((long) y * 100 / x);
    }
    
    // 이진탐색
    public static int binarySearch(int x, int y, int myScore) {
        int answer = -1;
        int start = 1, end = (int)1e9;
        
        while(start <= end) {
            int mid = (start + end) / 2;
            
            int newScore = getScore(x + mid, y + mid);
            if(myScore < newScore) {
                answer = mid;
                end = mid - 1;
            }else {
                start = mid + 1;
            }
        }
        
        return answer;
    }

    public static void main(String[] args) {
        Scanner sc  = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        int z = getScore(x, y);
        
        System.out.println(binarySearch(x, y, z));

    }

}