[Binary Search] 백준 2417번 : 정수 제곱근

[jeongabae]

실버4

시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 -- | -- | -- | -- | -- | -- 0.4 초 (추가 시간 없음) | 128 MB | 7891 | 1650 | 1354 | 28.338%

문제

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

입력

첫째 줄에 정수 n이 주어진다. (0 ≤ n < 2⁶³)

출력

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

예제 입력 1 복사

122333444455555

예제 출력 1 복사

11060446

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2006 0번

• 문제를 번역한 사람: baekjoon
• 데이터를 추가한 사람: doju, powergee, xkdlaldfjtnl, YunGoon

알고리즘 분류

• 수학
• 이분 탐색

내 제출

n=int(input())
start=0
end=n
while start<=end:
    mid=(start+end)//2
    if mid**2==n:
        start=mid
        break
    elif mid**2<n:
        start=mid+1
    else:
        end=mid-1
print(start)

start=0, end=n이라 두고 이분탐색 진행 만약 mid2==n이 되는 mid를 찾으면 이를 start값에 넣어주고 start출력 만약 mid2<n이라면 더 큰 값에서 찾아야 하므로 start=mid+1로 바꿔준다. 만약 mid*2>n이라면 더 작은 값에서 찾아야 하므로 end=mid-1로 바꿔준다. 왜 mid가 아닌 start를 출력하는지 설명해보자면, q^2 ≥ n인 가장 작은 음이 아닌 정수 q를 출력해야하므로 만약 n=143의 경우 제곱근이 11.9~~~...이므로 q=12여야 1212=144>143이 되어 답을 만족한다. 반복문 탈출 직전 start=11, mid=11, end=11이므로 mid**2<n이 되어 start=12, mid=11, end=11이된다 여기서 start를 출력해야 q^2 ≥ n인 q를 출력하는 것이 된다! 만약 mid를 출력해주면 q=11이 출력되므로 q^2<n이 되어 답을 만족하지 않는다.

내 풀이2 : 내장함수 이용

from math import ceil #올림함수 ceil
n=int(input())
q=ceil(n**0.5)
print(q)

사실 이 풀이가 제일 먼저 생각 났지만.... binary search이용해보래서 위에 처럼 먼저 품.

다른 사람 풀이 : 1등분 풀이

def search():
    n = int(input())
    sqr = int(n**0.5)
    if sqr**2 < n:
        print(sqr+1)
    else:
        print(sqr)

search()