[BaekJoon] "이진탐색" - 백준 2417번 문제 : 정수 제곱근

[문제 설명]

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

2417번: 정수 제곱근

 

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

q^2 >=n 인 가장 작은 음이 아닌 정수 q 출력

 

[해결 로직]

- 일단 0과 n의 중간값을 찾음(0: start, end : n, mid : 이 둘의 중간 값)

- 그러고나서 중간에 있는 값을 제곱했을 때, n보다 크다면 end를 mid-1로 설정

- 그 반대라면 start를 mid + 1로 변경

- 꽤나 쉬운 문제지만.. 제곱근으로 어떻게 중간값을 내지?? 라는 생각뿐이었던 것 같다

 

[Solution 코드]

n = int(input())

l,r = 0, n

while True:
    mid = (l+r)//2

    if r < l:
        break

    if mid ** 2 >= n:
        r = mid -1
    else:
        l = mid + 1

print(r+1)