RATIO 문제 이진 탐색으로 풀어봤는데 문제가 뭔지 잘 모르겠습니다.

  • 김동휘
    김동휘
    /*
    제가 생각해본 풀이방법입니다.
    
    1. 찾아 내야할 %수치가 어떤것인지 먼저 찾습니다.
    이것은(이긴횟수 / 총횟수) * 100 + 1 이라 생각했습니다.
    
    2. left값은 1로 두었습니다.right값은 최대 이긴 횟수 N으로 두었습니다.
    
    3. 이진 탐색을 진행했습니다.
    ㄱ.value라는 변수를 사용하여 mid값에 따른 현재의 %를 계산합니다     
    ㄴ.value == find일경우에
    min>mid 이면 min = mid로 갱신합니다. 
    그리고 right = mid - 1로 갱신합니다.더 작은 이긴 횟수를 찾기 위해서 입니다.
    
    ㄷ. value<find 인경우 left = mid+1로 갱신합니다. 
    ㄹ. value>find 인경우 right = mid-1로 갱신합니다. 
    ㅁ. min의 값이 변하지 않았다면 +1%를 만드는 연승 횟수가 존재하지 않으므로 -1을 출력했습니다. 
    ㅂ. 그 외의 경우에는 min값을 출력하였습니다. 
    
    
    */
    
    
    //#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    
    
    
    int main()
    {
    
    
    
        long long N, M;
        int i, j, T, k;
        long long value;
        long long find, min;
        long long left, right, mid;
    
    //  freopen("input.txt","r",stdin);
    
    
    
        scanf("%d", &T);            // 총 횟수
    
        for (k = 1; k <= T; k++)
        {
    
            scanf("%I64d %I64d", &N, &M);     // N은 총횟수 M은 이긴 횟수
    
            if (N == 0)                  //0으로 나눠질때의 예외 처리
                find = 0;
    
            else
                find = (M * 100) / N;           
    
    
            find = find + 1;  //우리가 원하는 1%가 올라간 수치.  즉 찾고자 하는 %값
            min = 3000000000;         // 나올 수 있는 가장 큰 값보다 큰값 설정
    
            left = 1;
            right = N;      //가장 오른쪽에 있는 값을 총횟수로 지정해주었습니다. 
    
            while (1)              // 이진 탐색을 통해 원하는 값을 탐색합니다. 
            {
    
                if (left>right) break;
    
                mid = (left + right) / 2;
    
                value = ((M + mid) * 100) / (N + mid);        
                // 탐색된 값의 %를 확인하고 find보다 작으면 mid보다 큰위치를 탐색
                // 같은경우 mid와 최소값을 비교하여 갱신
                // %가 큰경우 mid보다 작은 위치 탐색
                if (value == find)           
                {
    
                    if (min>mid)
                    {
                        min = mid;
                    }
    
                    right = mid - 1;
    
                }
    
                else if (value<find)
                {
                    left = mid + 1;
                }
    
                else if (value>find)
                {
                    right = mid - 1;
                }
    
    
            }
    
            if (min == 3000000000)
                printf("-1\n");
    
            else
                printf("%I64d\n", min);
    
        }
        return 0;
    
    }
    

    8년 전
2개의 댓글이 있습니다.
  • JongMan
    JongMan

    "이것은(이긴횟수 / 총횟수) * 100 + 1 이라 생각했습니다."

    꼭 이렇지 않습니다. ^^


    8년 전 link
  • 김동휘
    김동휘

    답변 감사드립니다!!!


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