백준 13706번 - 제곱근 / Python

문제: https://www.acmicpc.net/problem/13706

13706번: 제곱근

문제 설명

문제

정수 N이 주어졌을 때, N의 제곱근을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 양의 정수 N이 주어진다. 정수 N의 제곱근은 항상 정수이며, N의 길이는 800자리를 넘지 않는다.

출력

첫째 줄에 정수 N의 제곱근을 출력한다.

---

정답

n = int(input())


def binary_search(target):
    start = 1
    end = target
    while start <= end:
        mid = (start + end) // 2
        if mid ** 2 == target:
            return mid
        elif mid ** 2 > target:
            end = mid - 1
        else:
            start = mid + 1
    return None


print(binary_search(n))

 

---

풀이

 특정 정수의 제곱근을 구하는 문제입니다. n**. 5 나 math.sqrt()를 사용하시게 되면 오버플로우가 발생합니다. N의 길이가 800자 이하이므로 범위에 주의해야 합니다. 

n = int(input())

print(n ** 0.5)

  처음에는 위와 같은 사실을 생각 안 하고 간단하게 제곱근을 구했는데 바로 오버플로우가 발생했습니다. 그래서 알고리즘 분류에 맞게 이진 탐색으로 찾아보니 해결이 되었습니다.