-
이분 탐색 문제
-
처음 문제를 직면했을때 다른 방식으로 접근해 시간이 오래걸렸다. 우선, 단순히 z+1의 확률만 넘기면 된다고 생각하여 계산식으로 풀려고 했는데 그게 아니라 이분탐색으로 왼쪽 오른쪽의 수치를 비교해가면서 범위를 좁혀나가는 문제였다. 관련 이진탐색에 대해 깃헙에 개념을 정리해놓고, 관련 카테고리의 문제를 더 풀어야겠다.
import math
x,y = map(int,input().split())
z = y * 100 // x
if z >= 99:
print(-1)
else:
left, right = 1,x
answer = 0
while left <= right:
mid = (left + right) //2
z_new = (y+mid) * 100 // (x+mid)
if z_new > z:
answer = mid
right = mid - 1
else:
left = mid + 1
print(answer)