정수 제곱근 #2417

문제

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

입력

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

출력

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

예제 입력 1 복사

122333444455555

예제 출력 1 복사

11060446

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2006 0번

• 문제를 번역한 사람: baekjoon
• 데이터를 추가한 사람: doju, powergee, xkdlaldfjtnl, YunGoon

알고리즘 분류

• 수학
• 이분 탐색

---

 

import sys
n = int(sys.stdin.readline())
if n == 0:
    print(0)
    sys.exit()
start, end = 1, n
while start <= end:
    mid = (start + end) // 2
    if mid ** 2 >= n:
        end = mid - 1
    else:
        start = mid + 1
print(start)