백준 2417 - 정수 제곱근(파이썬)

문제

정수가 주어지면, 그 수의 정수 제곱근을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정수 n이 주어진다. (0 ≤ n < 2^63)

출력

첫째 줄에 q2 ≥ n인 가장 작은 음이 아닌 정수 q를 출력한다.

---

시나리오

처음엔 math라이브러리의 sqrt()함수를 호출한 것을 반올림해서 출력했지만 오답이 나왔다. 

그럴만도 한게 일괄적으로 반올림한다면 반올림 하지 않아야 정답인 케이스도 있을 수 있기 때문에 틀린 아이디어라고 할 수 있다.

그렇다면 탐색으로 접근해보자. 주어진 정수n의 크기는 2의 63제곱 즉, 900경 이상의 수가 나온다. 이를 완전탐색으로 일일이 돌면 당연히 풀 수가 없다.

하지만 log(2^63)은 43정도 밖에 되지 않으므로 이분탐색으로는 제한시간 내에 충분히 탐색가능한 수준이다.

따라서 1부터 n까지 어떤 수 m의 제곱이 n이 되는 m을 이분탐색으로 찾으면 되겠다.

코드

n = int(input())

lt = 1
rt = n
res = 0
while lt <= rt:
    mid = (lt + rt) // 2
    if mid * mid >= n:
        res = mid
        rt = mid - 1
    else:
        lt = mid + 1
print(res)