백준 1072번: 게임[JAVA]

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

1072번: 게임

 

 

 

[정답 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int X = Integer.parseInt(st.nextToken());
        int Y = Integer.parseInt(st.nextToken());
        int Z = (int) ((long) Y * 100 / X);
        int answer = -1;
        int left = 0;
        int right = (int) 1e9; // 범위는 문제에서 주어짐
        while (left <= right) { // left가 right를 넘어서면 종료
            int mid = (left + right) / 2;
            int newRate = (int) ((long) (Y + mid) * 100 / (X + mid));
            if (newRate != Z) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(answer);
    }
}

 

[설명]

이 문제는 이분탐색 문제이다. 처음에 이 문제를 풀 때 오른쪽 끝 범위를 몇으로 정해야 하는지 몰라 잠깐 막혔는데 문제에서 X의 범위는 10억이라고 정해줬다. 간단하게 알고리즘을 설명하자면

 

1. 범위내의 중간 값 mid 를 초기화해주고 X 외 Y 에 각각 mid를 더했을 때의 승률을 새로 구해준다.

2 - 1. 승률이 변했다면 횟수를 더 줄여야 하기 때문에 right = mid - 1 을 해준다.

2 - 2. 승률이 안변했다면 횟수를 더 늘여야 하기 때문에 left = mid + 1 을 해준다.

 

생각보다 간단한데 막상 아이디어가 떠오르지 않는다.