[C++][백준 1072] 게임

[문제]

https://www.acmicpc.net/problem/1072

1072번: 게임

[문제 풀이]

신경을 써줘야 하는게 많았던 문제.

숫자를 늘리면서 z가 바뀔때를 파악하면 되는데 단순히 1씩 늘리면서 파악하면 시간초과가 나기에 이분탐색을 써줘야 한다.

x의 범위가 10억까지라서 int로 계산을 하게 될 경우에 오류가 나는 경우가 많이 생긴다! (solve() 함수에 long long으로 x 와 y를 받아온 이유)

z가 99 이상이면 바뀌지 않는다.(반올림이 아니라 소수점을 버리기 때문에 99%가 절대 100퍼센트가 될 수가 없다.)

 

x의 최대 범위인 10억을 우측으로 0을 좌측에 주자.(13~14)

파악해야 하는건 최소로 변하는 값이기 때문에 z하고 범위를 최대한 줄여주자.(20~24)

이분탐색을 돌려주자.(16~26)

[코드]

#include<iostream>
#define endl "\n"
 
using namespace std;
 
void solve(long long x,long long y){
    long long z = (100 * y) / x;
    
    if(z>= 99){
        cout<<"-1"<<endl;
        return;
    }
    long long right = 1000000000;
    long long left = 0;
    
    while(left<=right){
        long long mid = left + right;
        mid = mid / 2;
        int temp = (100 * (y + mid)) / (x + mid);
        if(temp > z){
            right = mid-1;
        }
        else if(temp <= z){
            left = mid +1;
        }
    }
 
    cout<<left<<endl;
}
 
int main(){
    int x,y;
    cin>>x>>y;
    solve(x,y);
    return 0;
}