[BOJ] 백준 1072 - 게임 풀이

1. 문제

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

1072번: 게임

 

2. 풀이

이분탐색을 활용한 문제이다. 오랜만에 풀어서인지 개념이 기억나지 않아 찾아보던 중 좋은 분의 글이 있어서 참고하였다.

https://www.acmicpc.net/blog/view/109

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

 

우선 퍼센트를 구할 함수를 선언하고 현재까지의 승률을 구한다. 그 후 이분 탐색 알고리즘을 사용하여 반복을 돌 때마다 mid 값을 구하고 승률이 처음과 변하지 않았다면 결과에 mid값을 넣고 end 부분을 하나 줄인다. 이런식으로 first 값이 end 값을 넘어가면 반복문을 종료시킨다. 이때 주의해야할 점은 부동소수점에 대한 오차로 인해 틀리는 경우가 많으므로 자료형을 잘 생각해주어야 한다.

3. 소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

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 = getPercent(X, Y);

        int result = -1;
        int first = 0;
        int end = (int) 1e9;

        while (first <= end) {
            int mid = (first + end) / 2;

            if (getPercent(X + mid, Y + mid) != Z) {
                result = mid;
                end = mid - 1;
            }
            else {
                first = mid + 1;
            }
        }

        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
        br.close();
    }

    static int getPercent(int x, int y) {
        return (int) ((long) y * 100 / x);
    }
}