백준 02417번 / 2417번 문제 링크
문제 이름 : 정수 제곱근
주 언어 : Python
태그 : 수학 / 이분 탐색
solved.ac 등급 : Silver IV (2023/05/01 확인)
문제 보기
문제 :
정수가 주어지면, 그 수의 정수 제곱근을 구하는 프로그램을 작성하시오.
입력 :
첫째 줄에 정수 n이 주어진다. ($0 ≤ n < 2^{63}$)
출력 :
첫째 줄에 $q^2 ≥ n$인 가장 작은 음이 아닌 정수 $q$를 출력한다.
정직하게 이분탐색으로 풀어준다면,
low <= high일 동안, mid = (low + high) // 2로 잡고,
mid * mid == n이면 mid를 return 하고, mid * mid > n이면 high = middle - 1로 두고, 아니면 low = middle + 1로 둡니다.
최후에 low를 return 해주면 깔끔하게 풀 수 있습니다.
그러나, 파이썬에는 이런 기능을 하는 함수가 이미 math 모듈에 존재합니다.
파이썬 math.isqrt 함수 로 쉽게 풀어줄 수 있습니다.
isqrt 함수는 $p^2 \leq n$인 최대의 정수값 $p$를 return 함수이므로, 약간의 조절로 해당 문제에서 원하는 함수로 만들어 낼 수 있습니다.
다만, 입력이 0이 들어올 수 있으므로, 0인 경우에는 그냥 0을 출력하도록 해줍니다.
+) 왜 1 + math.isqrt(N - 1)이 $q^2 ≥ n$인 가장 작은 음이 아닌 정수 $q$인지는 해당 함수 설명에 적어두었습니다.
-번째 푼 문제 (2022/--/--)