99클럽 코테 스터디 1일차 TIL - 백준 1072 게임

• 단순하게 X와 Y를 1씩 증가했을 때, 시간초과가 발생한다.
• 이분탐색을 이용해 시간복잡도를 낮춘다.

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

public class BOJ_1072_게임 {
    public static void main(String[] args) throws IOException {

        // X: 1,000,000,000
        // Y: 1,000,000,000

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        long X = Long.parseLong(st.nextToken());
        long Y = Long.parseLong(st.nextToken());
        long Z = ((Y * 100l) / X);

        int start = 0;
        int end = 1000000000;
        long answer = -1;

        // 1부터 10억을 이진탐색
        while (start <= end) {
            int count = (start + end) / 2;

            long avg = ((Y + (long) count) * 100l) / (X + (long) count);

            if (avg != Z) {
                end = count - 1;
                answer = count;
            } else {
                start = count + 1;
            }
        }

        System.out.println(answer);

    }
}