(C++) - 백준(BOJ) 1072번 : 게임 답

www.acmicpc.net/problem/1072

1072번: 게임

최대 값 설정, 승률 계산 방식을 신경써 푼 기본 이분탐색 문제였습니다.

 

풀이방법

앞으로 할게임 수를 mid로 두어 z값이 바뀌는 최소값을 이분 탐색을 통해 찾습니다.

 1. 승률이 99%라면 게임을 아무리 많이해도 100%가 될 수 없으므로 -1을 반환합니다.

 2. 승률이 달라질 경우(기존 승률보다 ) r = mid - 1, 아닐경우 l = mid+1로 l<=r 인 동안 계속 l,r을 갱신해줍니다.

 3. 최종 l은 마지막으로 바뀌는 mid값에서 + 1되므로 이 값이 앞으로 해야할 최소한의 게임 수가 됩니다.

Code

#include <bits/stdc++.h>
#define ll long long
#define MAX 1000000000
using namespace std;
ll game,win;
ll binarySearch(){
    ll l = 0;
    ll r = MAX;
    ll firstZ = 100 * win /game;
    if(firstZ >= 99) return -1;

    while(l<=r){
        ll mid = (l+r) / 2;
        ll z = 100 * (mid+win)/(mid+game);
        if(firstZ < z) r = mid - 1;
        else l = mid + 1;
    }

    return l;
}
int main(){
    cin >> game >> win;
    cout << binarySearch() <<'\n';
}