[백준] 2417 정수 제곱근

🌭 문제 설명

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

---

🍗 제한 사항

---

🎁 입출력 예시

• 첫째 줄에 정수 n이 주어진다. (0 ≤ n < 2^63)

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

---

😎 나의 풀이

n = int(input())
s = 0
e = n
while s <= e:
    mid = (s + e) // 2
    if mid**2 < n:
        s = mid + 1
    else:
        e = mid - 1
print(s)

1. 이분탐색을 이용한 풀이다. 처음에는 math함수로 아주 간단하게 풀어보려했지만 당연히 시간초과
2. 탐색 범위를 [1,2^32] 까지로 잡고 (문제의 범위에 따라)
3. start와 end를 선언해준다.
4. mid를 제곱한 값이 n보다 작으면 mid의 값을 증가시키고 s에 할당해서 범위를 좁힌다 , n보다 크면 답 후보이기 때문에 e의 값을 할당한다.
5. s를 출력하면 정답

---

🧵 다른 풀이

from math import floor, sqrt

n = int(input())
i = floor(sqrt(n))

while i*i < n:
    i += 1

print(i)

1. 제곱근과 i의 값을 이용한 풀이다.

---

• 내가 처음에 풀었던 방식을 조금 수정하면 풀 수 있었던 문제였다. 이분탐색도 좋은 방법 인 것 같다.