[BOJ/1072번게임] c++ / binary_search

문제

게임 승률 Z가 변하기 위해 몇번의 게임을 더 이겨야 하는지 구하는 문제

 

생각

이긴 횟수를 0~ MAX까지 이분탐색해야겠다 생각함

 

문제풀이

1.st = 0, en = MAX 로 범위 설정

2.st <= en 일 동안, mid = ( st + en ) / 2 : 이긴 횟수 설정

3.Z_이 Z 보다 작을 경우, st = mid + 1; 이긴 횟수가 더 많도록 함

4.Z_이 Z 보다 클 경우, en = mid - 1; 이긴 횟수가 더 적도록 함

4-1.만약, min_mid 보다 mid가 작을 경우 min_mid = mid를 넣고 ck = 1 저장

5.ck = 1이면 min_mid 출력

5-1.ck = 0이면 -1 출력

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 1000000000
long long  X, Y, Z, st, en, mid, Z_, min_mid;
int ck = 0;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> X >> Y;
    Z =  (int)((Y * 100) / X ); // 처음 승률

    st = 0;
    en = MAX;
    min_mid = MAX;
    while ( st <= en ) {
        mid = ( st + en ) / 2;
        Z_ = (int)((( Y + mid ) * 100) / ( X + mid ));

        if ( Z_ <= Z )
            st = mid + 1;

        else {
            en = mid - 1;
            if ( mid <= min_mid ) {
                min_mid = mid;
                ck = 1;
            }
        }
    }
    if ( ck == 1 )
        cout << min_mid;
    else 
        cout << -1;
}

 

> 재채점

Z = (long double)Y / X * 100 으로 하면 틀림

Z =  (int)((Y * 100) / X ) 로 고쳐줌