[백준 | Java Silver IV] (#1072) 게임

문제

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

 

---

접근

처음에는 아래와 같이 count 변수를 두어서 하나씩 늘려가면서 찾으려고 했다.

int count = 0;
long newZ = Z;
while(newZ == Z){
    X++; Y++; count++;
    newZ = (int) ((double) Y/X * 100);
}

System.out.println(count);

 

하지만 이렇게 하면 틀렸고, X의 범위가 1부터 1,000,000,000 이기 때문에 최악의 경우는 10억의 승리 횟수까지 반복해야하기 때문에 시간 단축을 위해 이분 탐색을 통해 풀었어야 했던 문제이다. 

따라서 1부터 10억까지 이분탐색으로 빠르게 찾아내면 된다. 

 

(근데 주어지는 X 입력이 10억까지 가능한거고.. 10억 이상까지 갈 수도 있는거 아닌가.... 나만 애매한가)

 

최종코드

 

1. 승률 계산: (Y * 100) / X로 현재 승률을 계산
2. 이진 탐색: left와 right를 사용하여 가능한 범위를 탐색.
   1. newZ가 Z보다 클 때, result를 업데이트하고, right를 mid - 1로 설정하여 탐색 범위를 줄인다. 그렇지 않으면 left를 mid + 1로 설정하여 탐색 범위를 늘린다.
3. 결과 출력: 이진 탐색이 종료되면 result를 출력

 

package week12.baek.july23.baek;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class S1072 {
    public static void main(String[] args) throws IOException {
        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 = (long) ((double) Y/X * 100);

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

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

        while(left <= right) {
            int mid = (left+right) / 2;
            long newZ = (long) ((double) (Y + mid) / (X+mid) * 100);

            if(Z >= newZ) {
                result = mid + 1;
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }

        System.out.println(result);
        }
   }