[solved.ac 실버4] 2417_정수 제곱근 (파이썬, 이분 탐색)

 

제한 사항

 

문제

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

입력

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

출력

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

예제

 

---

나의 풀이

이분 탐색으로 풀이했다.

입력 조건에 보면 n은 0 ≤ n < 2^63 이기 때문에 나올 수 있는 답 중 가장 큰 값은 2^63의 제곱근이 되겠다.

그래서 end 초기 값을 3,037,000,500 정도로 시작했다. (파이썬이 아닌 언어를 사용하면 int와 같이 최대 21억 정도의 숫자를 담을 수 있는 자료형으로는 불가능하니 주의가 필요하다)

n = int(input())
start, end = 0, 3037000500
suspend = False
answer = 0
while start < end:
    mid = (start + end) // 2
    if mid ** 2 > n:
        end = mid - 1
    elif mid ** 2 < n:
        start = mid + 1
    else:
        answer = mid
        suspend = True
        break

if not suspend:
    answer = end + 1 if end*end < n else end
print(answer)

탐색 중에 제곱근을 만나면 suspend 변수에 True를 할당하고 answer에 mid를 저장하여 출력한다.

마지막까지 제곱근을 만나지 못했다면 end에는 제곱근과 가장 근접한 값이 들어 있을 것이다.

출력 조건이 q^2 ≥ n 이기 때문에 end의 제곱이 n보다 작으면 end + 1이, 그렇지 않으면 end가 답이 된다.

 

채점 결과