[jungol] Intermediate_Coder / 분할정복 / 1240 / 제곱근 / python

1240 : 제곱근

제한시간1000 ms    메모리제한32 MB    해결횟수739 회    시도횟수3640 회   

문제

   Korean    English  

임의의 정수 N이 주어졌을 때 N의 양의 제곱근의 정수부분을 출력하는 프로그램을 작성하라.

양의 제곱근이란 다음을 만족하는 수 X 를 뜻한다. 

 

 

N = X2 (X≥1)

 

 

 

[ 주의  !!! ] 

sqrt와 같은 함수를 사용하지 말아야 하며

stdio.h 와 iostream 등 입출력 헤더에 있는 함수만이 사용가능하다. 

이를 어길 경우 0점 처리한다.

 

입력형식

입력에는 263-1 이하의 양의 정수 N이 입력된다

 

출력형식

N의 제곱근의 정수부분을 출력한다.

 

입력1

8

출력2

2

입력2

16

출력2

4

 

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=523&sca=3010 

JUNGOL

 

🔥문제접근

1. N의 크기가 굉장히 크므로 이분탐색으로 효율성을 높히자

2. mid값을 구하고 mid의 제곱 <= N < (mid+1)의 제곱인 경우 라면 mid가 정수부이다.

3. mid의 제곱이 N보다 작은 경우 mid이하의 친구들은 체크할 필요가 없다.

4. mid의 제곱이 N보다 큰경우 mid 이상의 친구들은 체크할 필요가 없다.

👀코드구현

N = int(input())

start = 1
end = N // 2

def check(start, end):
    if N == 1:
        return 1
    mid = (start + end) // 2
    if mid**2 <= N < (mid+1) **2:
        return mid

    if mid**2 < N:
        return check(mid+1, end)
    else:
        return check(start, mid-1)

answer = check(start, end)
print(answer)