99클럽 코테 스터디 1일차 TIL 이분탐색(게임)

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

 

승률이 달라지기위한 게임 횟수를 구하는 문제였다.

처음엔 1부터 탐색했는데 생각해보니 X의 범위를 고려했을 때 최악의 경우 10억까지 탐색해야 했다. O(N)

따라서 이분탐색으로 풀어야 하는 문제였다. O(logN)

 

package STUDY;

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

public class Day01_BOJ_1072 {

    static int x, y;
    static int res;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        x = Integer.parseInt(st.nextToken());
        y = Integer.parseInt(st.nextToken());
        res = (int)((long) y * 100 / x);      // 초기 승률
        int left = 0;
        int right = 1000000000;
        int ans = -1;
        while(left <= right){
            int mid = (left + right) / 2;
            int tmp = (int)((long)(y+mid) * 100 / (x+mid));
            if(tmp != res){
                ans = mid;
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        System.out.println(ans);
    }
}

 

 

1. mid를 left와 right 중간 값으로 둔다.

2. 계산한 승률값이 초기 승률과 달라지면 mid보다 작은 범위에서 탐색해야 하므로 ans = mid로, right = mid - 1 로 설정한다.

3. 계산한 승률값이 초기 승률과 같다면 mid보다 큰 범위에서 탐색해야 하므로 left = mid + 1로 설정한다.

4. 설정한 범위가 교차하면 끝내면 된다!