1072번_게임_BOJ

문제 링크

1072번 게임 : https://www.acmicpc.net/problem/1072

문제 설명 및 해결 아이디어

주어진 게임횟수는 최대 1,000,000,000이다. 시간초과가 날 수 있기 때문에 Parametric Search로 접근해야 한다. 

mid를 게임횟수로 설정하여, 승률(Z)이 변할 때의 mid의 최소값이 문제의 출력이된다. 

코드

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long int
#define INF 9999999999999999
 
ll total, win;
ll originRatio, newRatio;
ll func() {
    ll left = 1, right = 1000000000;
    ll ret = INF;
    originRatio = win * 100 / total;
    while (left <= right) {
        ll mid = (left + right) / 2;
        newRatio = (win + mid) * 100 / (total + mid);
        if (originRatio < newRatio) {
            right = mid - 1;
            ret = min(ret, mid);
        }
        else
            left = mid + 1;
    }
    return ret;
}
 
int main() {
    while (scanf("%lld %lld", &total, &win) != EOF) {
        ll res = func();
        printf("%lld\n", res == INF ? -1 : res);
    }
 
    return 0;
}