RATIO 문제 코드 리뷰 부탁 드립니다.

  • kwangswei
    kwangswei

    RATIO 문제 풀이 중 입니다.
    예제의 답은 잘 나오는데 고려하지 못한 케이스가 있는 것인지 오답이 뜹니다.
    코드 리뷰 부탁 드립니다.

    풀이는 이분법을 써서 0 ~ 2000000000 범위 내에서 검색하는 것 입니다.
    upper 는 항상 가능한 답을 갖고 있고요.
    -1 처리는 목표 승률이 100을 넘을 때라고 생각 했습니다.
    입력 범위 내에서 2000000000 연승이면 무조건 1% 는 올릴 수 있기 때문에
    그 외에 -1 이 출력되어야 할 경우는 없을 것 같습니다.

    #include <iostream>
    #include <cmath>
    
    using namespace std;
    
    long long solve(long long N, long long M, int target);
    
    int main() {
        int T;
        cin >> T;
    
        while (T-->0) {
            long long N, M;
            cin >> N >> M;
    
            int target_ratio = (double)M / N * 100 + 1;
    
            if (target_ratio > 100)
                cout << -1 << endl;
            else
                cout << solve(N, M, target_ratio) << endl;
        }
        return 0;
    }
    
    long long solve(long long N, long long M, int target) {
        long long lower = 0;
        long long upper = 2000000000;
    
        while (lower + 1 < upper) {
            long long mid = (lower + upper) / 2;
    
            int ratio = (double)(M+mid) / (N+mid) * 100;
    
            if (ratio < target) {
                lower = mid;
            }
            else if (ratio >= target) {
                upper = mid;
            }
        }
    
        return upper;
    }
    


    11년 전
9개의 댓글이 있습니다.
  • Being
    Being

    정수 나눗셈으로 가능한 부분을 부동소수점으로 변환해 나누신 것이 문제가 아닐까 추측해 봅니다. :)


    11년 전 link
  • kwangswei
    kwangswei

    @Being 그 문제가 아니었습니다. ㅠ.ㅠ 뭐가 문제일까요 ㅠ.ㅠ


    11년 전 link
  • Being
    Being

    "입력 범위 내에서 2000000000 연승이면 무조건 1% 는 올릴 수 있기 때문에" 이 가정이 틀린 것 같습니다.


    11년 전 link
  • kwangswei
    kwangswei

    문제를 보면 "여기서 답이 되는 연승횟수는 2,000,000,000 이하라고 가정한다." 이기 때문에 2,000,000,000 연승이면 무조건 1%를 올릴 수 있을 것이고, 1%를 올릴 수 없는 경우는 이미 100% 일 경우라고 생각했습니다. 그리고 실제 N의 입력 범위도 1~1,000,000,000 이기 때문에 2,000,000,000 이면 적어도 1%는 무조건 올릴 수 있고요.. 구체적인 힌트를 부탁 드려도 될까요? ㅠ.ㅠ


    11년 전 link
  • Being
    Being


    우리가 지금 99%라면, 과연 100%로 올릴 방법이 있을까요? :)


    11년 전 link
  • kwangswei
    kwangswei

    헉......왜 그 생각을 못했을까요..... -_- ㅠ.ㅠ 너무 숫자 자체에 집중했네요 ㅠ.ㅠ


    11년 전 link
  • VOCList
    VOCList

    훈훈


    11년 전 link
  • Being
    Being


    \frac{a}{b} < \frac{c}{d} 이면 \frac{a}{b} < \frac{a+c}{b+d} < \frac{c}{d} 이지요..


    11년 전 link
  • kwangswei
    kwangswei

    정답 ㅠ.ㅠ
    Being님 감사합니다.
    갈 길이 머네요 휴우 ㅠ.ㅠ


    11년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.