[백준 알고리즘] 13706. 제곱근

 

 

 

처음에는 완전탐색 + 백트래킹을 사용했으나 가지치기가 제대로 안됐는지 시간초과가 떴다.

 

 

더 빠른 방법을 고민하다, 제곱근을 찾는 거라 이진탐색을 사용하면 좋을 것 같아 이진탐색을 이용해 풀었다.

 

 

 

# 이진탐색으로 해서 시간 단축

def binary_search(s, e):
    while True:
        mid = (s + e)// 2
        if (mid ** 2) == N:
            return mid
        elif mid ** 2> N:
            e = mid
        else:
            s = mid

N = int(input())
print(binary_search(1, N))