(매일 BOJ) C++ 1072번 게임

이번 문제는 1072번 게임이다.

접근법

이 문제는 정수 승률이기 때문에 변화가 일어나지 않을 수도 있다. 예를 들어,

• 현재 승률이 80%일 때, 1~수십 판 이겨도 여전히 정수 승률은 80%일 수 있다.

또한, 최대 10억 판 이상을 더 해야 바뀔 수도 있으므로 완전 탐색은 불가능하다.
따라서 이진 탐색(Binary Search)을 이용한다.

 

알고리즘 설계

1. 현재 승률 Z를 계산한다: Z = (Y * 100) / X
2. Z가 99 이상이면, 승률은 절대 1 이상 증가할 수 없으므로 -1 출력
3. 1부터 10억까지 이분 탐색 범위를 설정
4. mid값을 더 이긴 경기 수로 가정하고, 새로운 승률을 계산
5. 새 승률이 Z보다 크면 정답 후보로 저장하고, 더 적은 mid를 탐색
6. 아니면 mid를 증가시킴
7. 최솟값을 찾아 출력

작성코드

# include <bits/stdc++.h>
using namespace std;

int main (void){
    ios::sync_with_stdio(0); cin.tie(0);
    long long game_play, win;
    cin >> game_play >> win;
    int z = 100 * win / game_play;
    if (z >= 99) {
        cout << -1;
        return 0;
    }

    long long start = 1, end = game_play; 
    long long answer = 0;
    while (start <= end){
        long long mid = (start + end) / 2;
        long long new_z = (100 * (win + mid)) / (game_play + mid);

        if(new_z > z){
            answer = mid;
            end = mid - 1;
        }
        else{
            start = mid + 1;
        }
    }
    cout << answer;
}