[백준/Python] 13706번 제곱근

풀이

이분 탐색으로 양의 정수 N의 제곱근을 찾으면 됩니다. N의 길이가 800자리를 넘지 않는다는 것은 '10^800 - 1' 이 N의 최댓값이라고 볼 수 있습니다. N의 제곱근을 기준으로 이분 탐색을 할 것이기 때문에 '10^400' 을 N의 제곱근의 최댓값으로 잡고 이분 탐색을 하면 됩니다. (이보다 범위가 늘어난다 해도 이분탐색이기 때문에 탐색 속도에 큰 차이 없습니다.)

 

이분 탐색으로 N의 제곱근을 찾는거니까, mid의 제곱이 n 이 된다면 탐색 완료입니다.

 

import sys

n = int(sys.stdin.readline().rstrip())
start = 1
end = 10 ** 400

while start <= end:
    mid = (start + end) // 2
    if n == mid ** 2:
        print(mid)
        break
    elif n > mid ** 2:
        start = mid + 1
    elif n < mid ** 2:
        end = mid - 1