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일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.