백준 2417. 정수 제곱근 (with Python)

문제

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

접근 방법

일반적인 이진탐색으로 접근하여 해결했다.
조금 해맸던 부분은 q의 최소값을 구하는 부분이었다.

일단,
1. 시작점, 끝점은 0과 n으로 해주었다.
2. 시작점과 끝점을 통해 중간 지점을 구하고
3. 중간 지점의 제곱 값과 n을 비교했다.
4. 비교했을 때, n 미만이면 시작점 = 중간점 + 1
5. n 이상이면 끝점 = 중간점 - 1

이런 순서로 진행했다.
조금 생각했던 부분은 4번 5번에서 등호를 4번에 붙여야할지 5번에 붙여야 할지였다.

결과적으로 최소값을 뽑아줘야하니 등호를 빼주는 것이 맞는 것이었다.
(사실, 이분탐색은 아직 이해도가 높질 않아서 뚜렷하게 설명을 못하겠다...
조금 더 공부 할 필요성이 다분하다..ㅠㅠ)

코드

n = int(input())

s = 0
e = n

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

print(s)