문제

문제 링크

해설

• 게임 횟수(X)와 이긴 게임 횟수(Y)가 10억까지 입력 가능하고, 입력값에 따라 int 범위를 충분히 넘어갈 수 있기 때문에 안전을 위해 long long 또는 unsigned long long 자료형을 사용합시다.
• 승률 계산은 소수점을 버려야하므로 floor((double)Y * 100 / X)로 계산하면 됩니다.
• 승률이 절대 변하지 않는 경우는 어떤 경우가 있을까요? 정말 다행히 입력예시로 주어졌네요. 맞습니다. X와 Y가 같을 때는 승률이 절대로 변하지 않습니다. 따라서 X == Y 인 경우는 -1을 출력하고 프로그램을 종료하도록 예외처리를 반드시 해줍시다.
• for문을 돌면서 판 수를 1씩 늘려주면서 계산하면 시간초과가 발생합니다. 따라서 이분탐색을 사용합니다.
  • 현재 X의 최댓값은 10억이므로, 아무리 최악의 경우라도 5억판 정도 한다면 승률이 변할 것입니다.
  • 따라서 low = 1, high = 1e9로 설정한 뒤 이분탐색을 수행한 뒤, 승률이 변하는지 검사합니다.
  • 이런 방식으로 진행하면 정말 빠르게 계산할 수 있습니다. 아무리 최악이라도 반복문이 30~50번 밖에 안 돕니다.

코드

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

inline ll getZ(ll x, ll y) { return (y * 100) / x; }

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    ll X, Y;
    cin >> X >> Y;
    if (X == Y) { cout << -1; return 0; }
    
    ll Z = getZ(X, Y), low = 1, high = 1e9, mid, ans = -1;
    while (low <= high) {
        mid = low + (high - low) / 2;
        if (getZ(X + mid, Y + mid) > Z) high = mid - 1, ans = mid;
        else low = mid + 1;
    }
    cout << ans;
}

소스코드 링크

결과