유형정리(이분탐색) - 백준 2417

2417번: 정수 제곱근 (acmicpc.net)

2417번: 정수 제곱근

 

문제

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

입력

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

출력

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

예제 입력 1 복사

122333444455555

예제 출력 1 복사

11060446

 

 

문제를 안보고 선택을 했는데, 막상 문제를 보니 너무 간단하다. 문제 설명은 딱히 할 게 없어서 바로 풀이로 들어가겠다.

 

※ 알고리즘

1. n을 입력받는다.

2. 처음 값을 0, 마지막 값을 n으로 초기화한다.

3. 이분탐색 알고리즘을 작성한다.(mid 값으로 정수만 출력되어야 하므로 //(몫)으로 작성하고, mid^2 이 n 이상일 경우 마지막 값을 mid - 1로 설정하고, 아닐 경우 처음 값을 mid + 1로 설정한다.

4. 가장 작은 값이므로 갱신되는 first 값을 출력한다.

 

n = int(input())

first = 0
last = n

while first <= last:
    mid = (first + last) // 2
    if pow(mid, 2) >= n:
        last = mid - 1
    else:
        first = mid + 1

print(first)

 

이렇게 출력할 수 있다. last = mid + 1과 first = mid - 1을 설정할 때 헷갈릴 수가 있는데, 이분탐색 알고리즘을 짤 때는 설정한 조건의 반대편을 보는 것이 좋다. 큰 쪽이 조건으로 설정되면 마지막 값을, 작은 쪽이 조건으로 설정되면 처음 값을 건드린다고 생각하면 간단하다.