[백준 1072] 알고리즘 64일차 : 게임

www.acmicpc.net/problem/1072

1072번: 게임

 

C++ 이분탐색

(12분전)

앞으로 하는 게임은 모두 이긴다는 가정에서 최소 몇판을 더해야 승률이 변하는지 구하는 문제

99%일때와 100%일때는 아무리 게임을 더해도 승률이 절대 변하지 않는다 (-1출력)

X의 최댓값이 1000000000이라 추가로 더 하는 게임 횟수의 최댓값도 1000000000이다.

이분탐색의 범위는 1,1000000000

 

Z(승률) 구하는 식을 그대로 쓰면 50 29 일때 값이 틀리게 나온다

그래서 Y*100/X로 구해야하는데 Y/X를 할때 정수라 값 손실이 있어서 그런 것 같다.

범위는 int 범위인데 int로 하면 틀린다.

(이유는 자세히 찾아보진 못함 계산하는 중에 범위가 초과되서 그런것같은데..100%이해하진 못함)

 

소스코드

#include <iostream>
using namespace std;
long long X, Y;// X : 게임 횟수, Y: 이긴 게임
long long Z;

long long binarySearchMax(long long s, long long e){
    long long mid = 0;
    while(s <= e){
        mid = (s+e)/2;
        if((Y+mid)*100/(X+mid) > Z){
            e = mid-1;
        }else{
            s = mid+1;
        }
    }
    return s;
}
int main(){
    cin >> X >> Y;
    
    Z = (Y*100)/X;
    if(Z>=99){
        cout << -1;
        return 0;
    }
    cout << binarySearchMax(0, 1000000000);
    return 0;
}