반응형
문제: https://www.acmicpc.net/problem/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)
처음에는 위와 같은 사실을 생각 안 하고 간단하게 제곱근을 구했는데 바로 오버플로우가 발생했습니다. 그래서 알고리즘 분류에 맞게 이진 탐색으로 찾아보니 해결이 되었습니다.
반응형
'알고리즘 > 백준' 카테고리의 다른 글
백준 10815번 - 숫자 카드 / Python (0) | 2021.08.17 |
---|---|
백준 2417번 - 정수 제곱근 (0) | 2021.08.17 |
백준 18310번 - 안테나 / Python (0) | 2021.08.17 |
백준 1715번 - 카드 정렬하기 / Python (0) | 2021.08.17 |
백준 10825번 - 국영수 / Python (0) | 2021.08.17 |