문제

보다시피 다음과 같음. 요약하면 여태까지 x판해서 y판 이겼음. 이후 무조건 전승한다고 가정했을때 몇 승을 해야 승률이 변하는지 알아내라는 거였음.

-1 출력 조건

z가 변하지 않으면 -1 출력한다고 함.

소수점 아래는 버림. 따라서 승률이 99, 100% 라면 아무리 이겨도 승률이 변하지 않음. 99퍼라면 1번이라도 졌으니 아무리 이겨도 승률은 99.999xx일 것이며 문제에서 제시한 승률 구하는 공식은 소수점을 버리기 때문.

접근

그냥 0부터 무식하게 체크해보자.

미리 기존 승률을 구해놓고 y랑 x를 1 씩 올려가면서 새 승률을 구하는 거임. 소수점 아래를 버렸을 때 기존 승률과 차이가 있다면 스톱. 아니라면 패스 하는거.

파이썬 식 수도코드로 대강 작성해봄.

old = 기존_승률
answer = 0 
while True:
	all += 1
    win += 1
    answer += 1
    
    new = (win * 100 ) // all
    if new != old:
    	break
        
print(answer)
    

이 방식의 장점은 접근과 구현이 쉬움.
단점은 하나하나 체크하는거라 느림.

x의 범위가 아래와 같이 굉장히 크기 때문에 linear 하게 하나하나 체크하는 방식은 무조건 시간초과가 걸림.
x는 all임.
1 ≤ X ≤ 1,000,000,000

그러면 이분 탐색각 아님?

아무리 못해도 총 판수 만큼 플레이 하면 무조건 바뀜.

0판부터 처음 주어진 총 판수를 all 사이에서 조건을 만족하는 값을 찾으면 되겠다 생각이 들었음.

근데 조건은 위에 언급했다시피 x-1일때는 승률에 변화가 없지만 x일때는 변화가 있는 것임. 그걸 고려해서 구현해주면 됨.

기존 코드는 x일때 똑같지만 x+1일때 변화하는 값으로 구현해서 기준점이 다름을 알고 가면 좋음.

# 승률 구하는 함수
def get_calc(x,y,mid):
    tempX = x +mid
    tempY = y +mid 
    temp = (tempY * 100) // tempX
    return temp

# 정답 구하는 함수
def binary_search(old,x,y):
    start = 0
    end = x
    
    while start <= end:
    	# 중간 값 구해주기. 
        mid = (start + end) // 2
        
        # 현재 증가 수 일때 승률
        temp = get_calc(x,y,mid)
        
        # 현재 증강량 + 1 일때 승률
        temp2 = get_calc(x,y,mid+1)
        
        # 현재 증가수 일때 변화가 없는데 +1 한 건 변화가 있으면 +1 한게 당첨이라는 뜻. 그걸 반환
        if temp == old and temp2 != old:
            return mid+1
        
        # 둘다 승률 변화가 없으면 판수를 키워야한다는 뜻. start 올리기
        if temp == old and temp2 == old:
            start = mid + 1
		# 둘다 승률이 변하면 둘다 값이 지나치게 크다는거임. end를 내리기.
        if temp != old and temp2 != old :
            end = mid - 1
    
    # 여기엔 절대로 도달하면 안됨.
    raise Exception

결과