(Python) - 백준(BOJ) 13706 : 제곱근

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

13706번: 제곱근

이분탐색 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

n을 선언 후 입력받습니다.

📔 풀이과정

n이 800자리이므로 big int가 지원되는 언어가 구현하기 쉽습니다.

math.sqrt함수로는 800자리의 n을 인자로 받을 수 없습니다. overflowerror를 출력하므로 틀리게 됩니다. 해당 issue는 하기 링크에 있습니다.

https://stackoverflow.com/questions/28239978/python-sqrt-limit-for-very-large-numbers

Python sqrt limit for very large numbers?

 

따라서 이분탐색으로 제곱근을 판별해줍니다. 함수 binary_search()를 실행해 정답을 구합니다.

📔 정답출력

binary_search()의 반환값을 출력합니다.

---

📕 Code

from pickletools import long1
import sys
input = sys.stdin.readline
n = int(input())

def binary_search():
  s = 1
  e = n
  while s <= e:
    mid = (s + e) // 2
    if(mid ** 2 <= n): s = mid + 1
    else: e = mid - 1
  return e

print(binary_search())