[백준 1072번] 게임 (C++)

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

1072번: 게임

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int X, Z;
ll Y;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> X >> Y;

    Z = Y*100/X;
    if(Z>=99) //승률 100퍼는 불가능
    {
        cout << -1;
        return 0;
    }

    int l=0, r=1000000000;

    while(l<=r) //이분 탐색
    {
        int mid = (l+r)/2;
        int tmp = (Y+mid)*100 / (X+mid); 
        
        if(Z>=tmp)
        {
            l = mid + 1; 
        }
        else 
        {
            r = mid - 1;
        }
    }

    cout << l;

    return 0;
}

형택이가 게임을 이길 때도 있지만, 이미 졌을 때도 있었으므로 승률 100퍼는 불가능하다.

따라서 승률을 나타내는 Z 값이 99이상일때는 바로 -1을 출력하고 종료한다.

 

이후는 단순 계산을 하면 시간초과가 발생하기에 이분 탐색을 사용한다.

먼저 목표값 mid는 추가로 시행한 게임 횟수이다.

해당 게임 횟수는 무조건 이긴 게임이며 기존 확률을 구하는 계산식에 있는 X, Y에 각각 mid 값을 더해여 새롭게 확률을 구한다. 

 

앞으로 모든 게임을 이기기에 확률이 변하는 경우는 무조건 Z가 새롭구 구한 확률인 tmp보다 커야 한다.

이 경우 이분 탐색의 좌측 포인터인 l의 값을 mid + 1로 변경하는데 변경하는 동시에 해당 값이 조건을 만족하는 횟수이기도 하다.

 

만족하는 횟수를 찾아도 그 값이 최소라고 보장할 수는 없기에 계속해서 이어서 탐색하며 범위를 좁혀 최소값을 찾고 이렇게 저장된 l의 값을 출력해준다.

 

추가적으로  (Y+mid)*100을 하는 과정에 int 범위를 초과하는 경우가 생겨 Y를 long long으로 선언해주었다.