백준 1072 - 게임 - 이분 탐색

문제

문제링크 : https://www.acmicpc.net/problem/1072

풀이전략

1. 승률을 계산할때 100을 곱해주고 나누는 방법을 사용하는데 이때 오버플로우가 나지 않도록 long long으로 변수를 선언해주어야한다.
2. 승률이 변하는지 아닌지를 확인해보려면 rt에 지금까지 했던 횟수를 넣어주면 된다.
3. 게임을 더 하는 횟수가 결국 이분 탐색으로 찾을 값이다.

코드

#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;

long long X, Y, Z;

bool isChange(long long win, long long total){
    /// 여기서 win*100 하는 순간 오버플로우가 나올 수 있음 이런거 까지 생각해야함
    long long val = (win*100)/total;
    if(val > Z) return true;
    else return false;
}
int res = 2147000000;
int BinarySearch(long long lt, long long rt){
    if(lt> rt){
        return res;
    }
    else{
        long long mid = (lt+rt)/2;
        if(isChange(Y+mid, X+mid)){
            if(mid < res) res = mid;
            return BinarySearch(lt, mid-1);
        }
        else{
            return BinarySearch(mid+1, rt);
        }
    }
}

int main(){

    // freopen("../input.txt","rt",stdin);
    
    scanf("%lld %lld",&X, &Y);
    Z = (Y*100)/X;
    int ret = BinarySearch(1, X);
    if(ret == 2147000000) printf("-1\n");
    else printf("%d\n",ret);
    return 0;
}

소감

이 문제도 왜 이분탐색이지?? 라는 생각을 했었다. 하지만 차근히 생각하고 왜 이분탐색인지를 생각해서 알아내야한다. 또한 평균을 구해줄때 100을 곱해준다 이때 long long으로 해주어야 한다.

실수하기 좋은 문제였다.