백준 13706번: 제곱근 (Python)

https://www.acmicpc.net/problem/13706

13706번: 제곱근

---

Solved By: Binary Search

 

주어지는 수가 엄청 크기 때문에 Python을 이용했습니다. Python의 math 패키지에 있는 sqrt를 사용하여 문제를 풀려 했지만 연산을 해야 하는 값이 너무 커서 OverflowError가 나왔습니다.

 

그래서 이분 탐색을 돌려서 만족하는 값이 있으면 출력하도록 코드를 썼습니다.

from math import sqrt

n = int(input())
low, high = 1, n

while low <= high:
    mid = (low + high) // 2
    #print(mid)
    
    if(mid * mid < n):
        low = mid + 1
    elif(mid * mid > n):
        high = mid - 1
    else:
        print(mid)
        break