RATIO (하, p. 476)

문제#

어떻게 풀었나?#

바이너리 서치로 풀었음.

정답 코드#

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        ll n,m;
        cin >> n >> m;

        ll s = m*100LL/n;
        ll lo=0, hi=2e9+1;
        while(lo<=hi) {
            ll mid = (lo+hi)/2;
            ll x = (m+mid)*100LL/(n+mid);
            if(x>=s+1) hi=mid-1;
            else lo=mid+1;
        }

        if(hi==2e9+1) puts("-1");
        else printf("%lld\n", hi+1);
    }
    return 0;
}

Comment#

본 문제는 문제 난이도에 비해 괴랄한 정답률을 보여주고 있다.

댓글만 봐도 “왜맞틀”을 시전하는 사람들이 많은데, 딱 봐도 감이 온다. “어디서 틀렸는지”

1. 아마 double type을 썼을 것이다.#

소수 연산은 항상 오차가 있고, 문제에선 오차 인정을 해주지 않기 때문에 double 타입을 절대 써서는 안된다. int형 변수간의 나눗셈 연산은 정수형 나눗셈에 해당하고 이는 ‘부동소수점’을 가지고 하는게 아니다. 그러니 쓸데 없이 int형 나눗셈 연산에 double로 강제 타입변환하는 바보짓은 하지 말자.

2. *100을 먼저해야 한다.#

double 타입을 쓰지 않기에, 나눗셈만 먼저하게 되면 항상 값은 0이되고 여기에 100을 곱해봐야 값은 항상 0이 나온다. 이런 경우에 오면 초보자들이 가장 많이 하는 실수가 나눗셈 자체를 (double) 결과로 만드는 것이다. 만약 double type을 쓰지 않아야겠다고 생각한 사람이라면 꼭 100을 먼저 곱해서 AC를 받았겠지만, 그게 아니라면 (double)(m+mid)/(n+mid)*100 이라 쓰고 WA를 받았을 것이다.

3. long long type을 써야 한다.#

int변수를 사용하면서 long long으로 타입 강제변환 하지 않는 경우, 위에서 언급한 것과 같이 *100을 먼저하게 되므로 int범위를 초과하게 된다. 그러니 그냥 처음부터 long long 변수를 사용하면 된다.

4. binary search의 lo, hi지정을 잘 해야 한다.#

binary search시 항상 찾을 수 있는 경우의 문제도 있지만, 이 문제는 그렇지 않다. 최대 연승횟수 20억을 초과하는 경우 더이상 탐색할 필요가 없고, 실제로 탐색이 끝난 뒤 탐색 결과가 없음을 잘 표시해야한다. 방법은 여러가지 있겠지만, 위의 정답 코드와 같이 hi값을 문제에서 주어진 20억보다 1만큼 더 쓰면, 나중에 탐색 결과hi값이 20억+1일 때 “탐색 결과, 아무것도 찾지 못함”을 잘 캐치할 수 있다.