문제

문제 링크

문제 접근

  • 이 문제는 보자마자 바로 이분 탐색으로 풀어야겠다는 생각이 팍 왔다.
  • z가 99나 100인 경우는 하나 더 올리는 게 불가능하기 때문에 그 경우에는 -1을 출력하게 하고 나머지 경우에 대해서 이분 탐색을 진행하였다.

이분 탐색

  • 먼저 이분탐색을 진행하기 left와 right를 정하였다.
  • 주어진 X의 최대값 10억일때 승률 1퍼를 올리기 위해서는 10억판이 필요하다.
  • 때문에 left는 1, right은 10억으로 설정했다.
  • 매 경우마다 mid를 찾아주고 mid를 이용해서 승률(val)을 구해서 이를 원하는 승률(z)과 비교했다.
  • 구한 승률이 원하는 승률보다 크거나 같을 때는 right 낮춰주고 작을 때는 left를 높여주었다.
  • 우리가 찾고자하는 것은 원하는 승률을 찍는 판수의 최소값이기 때문에 lower_bound로 right를 변경할 때 ans를 업데이트 하도록 하였다.

코드

#include <cstdio>
int main(){
    long long x, y, z, ans = -1;
    scanf("%lld %lld", &x, &y);
    z = y*100 / x + 1;
    if(z == 100 || z == 101){
        printf("-1");
        return 0;
    }
    long long l = 1, r = 1000000000;
    while(l <= r){
        long long mid = (l + r) / 2;
        long long val = (y + mid)*100 / (x + mid);
        if(z <= val) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    printf("%lld", ans);
}

느낀점

  • 아직도 이분탐색은 여러번의 제출을 거듭해야 정답을 구할 수 있었다.
  • 한번에 정답을 확 도출해낼 수 있으면 좋겠다!