백준 2417 - 정수 제곱근(Python3)

문제

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

입력

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

출력

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

예제 입력 1 복사

122333444455555

예제 출력 1 복사

11060446

 

풀이

n = int(input())

low = 0
high = 2 ** 32
ans = -1
while low <= high:
  mid = (low + high) // 2
  if mid ** 2 < n:
    low = mid + 1
  else:
    ans = mid
    high = mid - 1

print(ans)

 

해당 문제는 이분 탐색을 사용하여 해결하였다. n의 범위가 0이상 2의 63승 이하이다. 제곱근을 구하므로 최솟값을 0 최댓값을 2의 32승으로 설정하여 둘의 중간값의 제곱을 n과 비교하여 반복하여 해결하였다.

 

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