[Python/파이썬] 백준 2417번 정수 제곱근

2417번: 정수 제곱근

 

코드

n = int(input())

s, e = 0, n
ans = 0
while s <= e:
    mid = (s+e)//2
    if mid ** 2 < n:
        s = mid+1
    else:
        ans = mid
        e = mid-1
print(ans)

 

큰 범위에서 조건에 만족하는 수를 찾을 때는 매개 변수 탐색을 하면 된다. 이 방법의 시간 복잡도는 O(logN)으로 최대 크기인 2^63이 들어오더라도 빠르게 q^2 ≥ n인 가장 작은 정수 q를 찾을 수 있다.