[Algorithm]Baekjoon 1072번 :: 게임

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
long long x, y, z;
 
bool check(int mid)
{
    long long tempY = y + mid;
    long long tempX = x + mid;
    long long winRatio = (tempY * 100) / tempX;
 
    if (winRatio > z) return true;
    return false;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> x >> y;
 
    z = (y * 100) / x;
 
    if (z >= 99)
    {
        cout << -1;
        return 0;
    }
 
    long long left = 1;
    long long right = 1000000000;
    int answer = 0;
 
    while (left <= right)
    {
        int mid = (left + right) / 2;
 
        if (check(mid))
        {
            right = mid - 1;
            answer = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
 
    cout << answer;
}
 
 
 

 

 

실수문제를 많이 다뤄보지 않았다면 헤맬 수 있는 문제..

다들 한번씩은 들었겠지만, 컴퓨터는 부동소수점을 정확하게 표현하지 못한다.

결국 2^-n승의 숫자들의 조합으로 소수를 표현하기 때문에, 오차가 발생할 수 밖에 없다.

그러면 이 오차를 최대한 줄여야하는데, 그 방법중 하나가 나누기를 할 때 최대한 큰수를 작은수로 나누는것이다.

 

승률을 계산할 떄 보통  (이긴 횟수 / 전체 판수) * 100 하는 식으로 계산을 할 것이다.

이 때, 나눈다음에 *100을 하기보다는 처음부터 이긴횟수 * 100을 먼저해준다음 전체판수로 나눠주는 것이다.

 

마지막으로 주의해야할 점은, 처음에 주어지는 x,y에 대한 승률이 99프로 이상일 경우 그냥 바로 -1을 출력해줘야 한다는 것이다.

승률이 이미 99프로면, 아무리 게임을 많이하더라도 절대 100퍼가 될 수 없다.

100퍼는 반드시 이긴횟수와 전체판수가 동일해야하기 때문이다.