[S4] 백준 2417 - 정수 제곱근 (python3)

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

2417번: 정수 제곱근

 

---

해결방법

정수 제곱근을 구하기 위한 풀이 전략

0과 n(n>=0) 의 중앙값의 제곱이 n과 같은지, 큰지, 작은지를 따져보며 q를 구해내는 해결 방법이다.

n과 m의 중앙값의 제곱은 앞으로 'n과 m의 중앙제곱'이라고 부르겠다.

 

1. 만약 0과 n의 중앙제곱이 n과 같다면 그 값이 정답이다. ( 0과 4의 중앙제곱 = 2,  2^2 = 4)
2. 만약 0과 n의 중앙제곱이 n보다 크다면 mid와 n의 중앙제곱을 비교한다.
3. 만약 0과 n의 중앙제곱이 n보다 작다면 0과 mid의 중앙제곱을 비교한다.

위 조건문 안에서는 low와 high를 업데이트 해주는 작업도 반드시 한다. 그리고 문제 조건이 "q^2 ≥ n인 가장 작은 음이 아닌 정수 q"이기 때문에 n이 제곱수가 아닌 경우에 n보다 큰 제곱수들 중에서 가장 작은 제곱수의 제곱근을 내뱉어야 한다. 그렇기 때문에 2번 조건에서 answer을 업데이트 해주어야 한다.

 

예를 들어 n = 105 라면 n보다 큰 제곱수는 121(=11^2)이다. 따라서 문제에서 원하는 정답은 11이다.

이 풀이는 우리 머리로 암산 가능한 작은 수에서는 통하지만 입력으로 주어지는 n의 최대값은 2^63-1 이므로 미리 코드를 짜두기란 쉽지 않다.

 

위 과정을 반복하여 정답을 구한다.

풀이👀

기본 로직은 이분탐색이니 아래 그림을 따라가보며 n=100 일때의 동작 과정을 살펴보자.

lo는 작은 값, hi는 큰 값, mid는 lo와 hi의 중앙값( (lo+hi)/2 )이다.

 100의 제곱근은 정수 10이라서 위 처럼 깨끗하게 해를 구한다.

하지만 100과 121 사이의 정수가 n으로 주어진다면?

아마 위 그림에서 10-13 사이의 중앙값(23//2) 11일때 다시 계산해보고, 3번 조건을 통과하여 3번 안에서 answer을 업데이트 해준다. 탐색을 종료하면 11을 출력할 것이다.

---

코드🐱‍👓

n = int(input())

lo, hi = 0, n

ans = max(lo, hi)

while lo+1 < hi:
    mid = (lo + hi) // 2
    comp = mid**2
    if comp == n:
        ans = mid
        break
    elif comp > n:
        ans = min(ans, mid)
        hi = mid
    elif comp < n:
        lo = mid

print(ans)

코드 설명

		ans = min(ans, mid)

이 코드가 이해가 잘 안 될 수 있겠다고 생각했다. 어째서 answer은 answer과 mid 중 더 작은 값이 정답인 걸까?

그 이유는 최대한 작은 수들 중에서 주어진 조건을 만족하는 수를 찾기 위해서이다.

 

n이 제곱수가 아니면 정수 q를 제곱했을 때 n이 절대 나올 수 없기 때문이고, q제곱이 n보다는 커야 하기 때문이다.

---

무려 8달만에 풀었다..!