[Silver IV] 제곱근 - 13706

문제 링크

성능 요약

메모리: 31256 KB, 시간: 56 ms

분류

임의 정밀도 / 큰 수 연산, 이분 탐색, 수학

문제 설명

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

입력

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

출력

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

---

풀이

아이디어

이걸 어떻게 풀까 라는 생각이 들었고, 그냥 sqrt()로 일단 질러보기로 했다. (파이썬은 위대하니까...!) 하지만 OVERFLOW가 났고, 이분탐색을 할 수 있는 수학적 방법을 찾아보았다.

단순히 0부터 입력값까지 탐색을 진행해서 제곱을 한뒤 풀이 할 수 있겠다는 아이디어를 가진건 나중이었다..

홍길주의 숙수념이라는 개념으로 풀이하였다

홍길주의 숙수념 : 제곱근을 구하려는 값 $m$을 2로 나눈뒤 $i\text\{i:1,2,\cdots\}$를 $m$에서 빼준다.
이때 가장 먼저 음수가 되도록하는 $i$ 값이 정답이다.

이때 $i$ 값은 $\sum_{i=1}^{\frac{m}{2}}i$ 이므로 이를 매개변수 탐색을 이용하여 풀이한다.

코드

val = int(input())//2

start, end = 0, val // 2
calc = lambda n: (n * (n-1)) // 2
while start <= end:
    mid = (start + end) // 2
    if calc(mid) < val:
        start = mid + 1
    else:
        end = mid - 1
print(end)

---

회고

특이한 개념을 알았고, 이를 구현했을때 뿌듯하였다.