/*제가 생각해본 풀이방법입니다.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>intmain(){longlongN,M;inti,j,T,k;longlongvalue;longlongfind,min;longlongleft,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;elsefind=(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;}elseif(value<find){left=mid+1;}elseif(value>find){right=mid-1;}}if(min==3000000000)printf("-1\n");elseprintf("%I64d\n",min);}return0;}
김동휘
9년 전