Ratio 문제 계속 오답이 나네요 ㅠㅠ

  • SabZzil
    SabZzil

    안녕하세요 질문 읽어주셔서 감사합니다.
    Ratio 문제를 풀고 있는데 어려움이 있어서 질문 올립니다.
    입력받은 승률을 t라는 long long 변수에 

    t = (long long)((100LL*m)/n);

    이런 방식으로 저장하고 t++로 1증가시켜서

    t+1 이 100이면 -1을 출력(더이상 승률을 높힐 수 없기 때문)

    100이 아닌 경우에는
    a 라는 long long 변수에 (m+a)/(n+a) >= t 를 만족시키는 값

    a = (long long)((t*n-100LL*m)/(100LL-t));

    를 계산 한 뒤 a의 값을 1씩 증가시키면서
    (100LL*(m+a))/(n+a) 의 값이 t+1보다 같거나 큰지 확인하는
    방식으로 알고리즘을 구현하였는데 계속 오답이 뜨네요 ^^;

    아래는 제가 사용한 코드이고, 그 밑에는 랜덤 숫자를 생성해본 코드입니다.
    몇일째 고민해도 답이 잘 안나와서 힌트를 좀 얻고자 글 올립니다.
    감사합니다.

    #include <stdio.h>
#include <string.h>

int main() {
    int c;
    scanf("%d", &c);

    while(c--) {
        long long n, m, a;
        long long t, test;
        int f = -1;
        scanf("%d %d", &n, &m);

        t = (long long)((100LL*m)/n);
        t++;

        if(t>=100LL) {
            printf("%d\n", f);
            continue;
        }

        a = (long long)((t*n-100LL*m)/(100LL-t));

        while(1) {
            test = (100LL*(m+a))/(n+a);
            if(test>=t) {
                break;
            }
            a++;
        }


        printf("%lld\n", a);

    }
}

    랜덤으로 생성해본 숫자는 아래와 같습니다.
    이렇게 생성해서 많은수에 대해서 테스트 해봤는데도 문제점을 찾지 못했는데 어디가 잘못된 것일까요 ?

    n = (long long)((double)(rand()<<15|rand()) / ((RAND_MAX<<15|RAND_MAX)+1) * (1000000000));

m = (long long)((double)(rand()<<15|rand()) / ((RAND_MAX<<15|RAND_MAX)+1) * (n));

    8년 전
1개의 댓글이 있습니다.
  • Corea
    Corea 
    test = (100LL*(m+a))/(n+a);
if(test>=t) {
    break;
}

    위 부분에서 소수점 연산의 오차로 인해 값이 정확하지 않을 수 있습니다. 최대한 정수로 비교를 해주시면 좋을 것 같네요. 위 코드를 수정하여 제가 제안하는 코드는 다음과 같습니다.

    if((m+1) * 100 >= t * (n+a)) {
    break;
}

    하지만 제안하신 방법으로 문제를 해결하실 수는 없습니다. 이분 탐색을 응용하면 해결하실 수 있는데, 자세한 내용은 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 책을 살펴보세요.


    8년 전 link

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