[백준] 1072 게임

1072번: 게임

 

www.acmicpc.net

풀이

해당 문제는 이분 탐색으로 해결할 수 있다. mid 값을 '형택이가 앞으로 하게될 게임의 개수'로 잡고 이분 탐색을 하면 된다. 승률 Z는 (Y x 100) / X 로 구할 수 있는데, 이 때 주의해야할 것은 Y x 100이 int 범위를 벗어날 수 있기 때문에 long long형으로 선언해야한다.

코드

#include <iostream>
#include <limits>
#include <algorithm>
using namespace std;

long long x, y;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> x >> y;

    int left = 1;
    int right = 1000000000;
    int ans = numeric_limits<int>::max();
    int z = (y * 100) / x;

    while (left <= right) {
        int mid = (left + right) / 2;

        int tmp_z = ((y + mid) * 100) / (x + mid);
        if (z < tmp_z) {
            right = mid - 1;
            ans = min(ans, mid);
        }
        else {
            left = mid + 1;
        }
    }

    if (ans == numeric_limits<int>::max()) cout << -1 << '\n';
    else cout << ans << '\n';
    return 0; 
}