[BOJ | Python] 2417번: 정수 제곱근

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

 

문제

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

 

 

입력

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

 

 

출력

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

 

풀이

이분탐색을 사용해서 풀이했다.

n = int(input())
left, right = 0, n

while left <= right:
    mid = (left + right) // 2
    val = mid ** 2

    if n <= val:
        ans = mid
        right = mid - 1
    else:
        left = mid + 1

print(ans)

문제에서의 q의 역할을 mid가 임시적으로 수행한다.

만약 mid^2이 n 이상이라면 조건을 충족하므로 ans에 mid의 값을 저장한다. 조건을 충족했지만, 우리는 조건을 충족하면서 '가장 작은' 정수를 찾아야 하므로 right를 mid - 1로 줄인 후 다시 검사한다.

반대로 조건을 충족하지 않는다면 mid 값이 더 커져야 하므로 left를 증가시킨다.