[Python] 백준 2417번

2417. 정수 제곱근 (silver 4)

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

 

입력

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

 

출력

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

 

예제 입력1

122333444455555

 

 

예제 출력1

11060446

 

 

 

풀이)

이분 탐색 방법을 사용했다.

시작점에 해당하는 start는 0, 끝점에 해당하는 end는 입력값인 n으로 저장해주었다.

while문을 사용해서 mid값을 시작값과 끝값의 중간 값으로 저장해주었고, if문을 사용해서 중간값의 제곱값이 n 미만이면 시작점을 중간값보다 1크게 저장해서 다시 탐색하도록 했고, 중간값의 제곱값이 n이상이면 끝점을 중간값보다 1 작게 저장해주었다,

n = int(input())

start = 0
end = n

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

print(end+1)