[백준 2417번] 정수 제곱근

문제 링크

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

 

문제 요약

문제에서 주어진 N의 제곱근을 소수점에서 올림 한 값을 구하는 문제이다.

 

함정이 가득한 문제

문제 자체는 상당히 간단해 이제 막 PS에 입문한 사람들이 연습용으로 풀기 좋은 문제로 보인다. 그리고 문제 번호도 2000번 대여서 뭔가 연습문제 같은 느낌도 상당히 든다.

???: 제곱근을 수하고 소수점에서 올림을 하라니?! sqrt 함수를 이용하면 그냥 풀 수 있는 문제잖아!

 

이런 생각의 흐름을 거치고 나면 아래와 같은 코드를 작성하고 제출을 누르게 된다.

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    unsigned long long n;
    
    cin >> n;
    
    unsigned long long ans = sqrt(n);
    
    if (ans * ans == n) {
        cout << ans << endl;
    } else {
        cout << ans + 1 << endl;
    }
}

그렇게 나에게 주어지는 틀렸습니다 목걸이...!!

 

그렇다... 이 문제는 누구나 풀 수 있는 문제인 것처럼 사람들을 유혹하지만 사실은 함정이 가득한 악마의 문제인 것이다. 이제 이 문제를 어떻게 풀면 좋을지 알아보자.

 

문제 풀이

sqrt 함수는  내부적으로 float, double, long double 자료형을 이용한다. 이런 자료형들을 부동 소수점을 사용하고 약 15~19자리까지 정확하다고 알려져 있다. 그런데 입력으로 주어지는 N의 최댓값은 \(2^{63} - 1\)이고 이는 20자리이다. 즉 정확하게 계산할 수 있는 범위를 넘어서기 때문에 정답을 구할 수 없는 것이다.

 

정확한 정수 제곱근을 구하기 위해서는 직접 계산하는 방법이 필요하다. 여기서는 이분 탐색을 이용한 방법을 설명한다.

1. lo를 0, hi를 적당히 큰 값으로 설정한다.
2. lo와 hi의 중앙값인 mid를 계산한다.
3. mid의 제곱이 N보다 작으면 lo를 mid + 1로 설정한다.
4. mid의 제곱이 N보다 크거나 같으면 hi를 mid로 설정한다.
5. lo가 hi보다 커질 때까지 2, 3, 4를 반복한다.

이와 같이 이분 탐색을 이용해 sqrt 함수의 한계를 극복하고 정확한 정수 제곱근을 구하면 맞았습니다!! 목걸이를 받을 수 있다.

 

소스 코드

#include <stdio.h>

unsigned long long n;

int main() {
    scanf("%llu", &n);
    
    unsigned long long lo = 0, hi = 4294967296;
    
    while (lo < hi) {
        long long mid = (lo + hi) / 2;
        
        if (mid * mid >= n) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    
    printf("%llu\n", lo);
}