[백준/Python] 2417번: 정수 제곱근

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

2417번: 정수 제곱근

---

---

문제 분석

문제 그대로 정수가 주어지면, 그 정수의 제곱근을 구하는 문제이다.

n의 범위가 (0 ≤ n < 2⁶³)이므로 범위가 넓기 때문에 하나하나 다 탐색하여 제곱근을 찾기에는 시간이 부족하다.

그렇기 때문에 이분 탐색 알고리즘을 사용하여 시간을 줄여 문제를 해결하자

 

---

코드

n = int(input())

start, end = 0, n
result = 0

while start <= end:
    q = (start + end) // 2

    # q의 제곱값이 입력값보다 작은 경우 답이 될 수 없음
    if q**2 < n:
        start = q + 1
    # q의 제곱값이 입력값보다 크거나 같은 경우 result에 값을 넣고 최소를 찾음
    else:
    	# 크거나 같을 때만 조건이 만족하므로 마지막에 저장되는 값이 가장 최소
        result = q
        end = q - 1

print(result)