[백준] 2417번 - 정수 제곱근 [Java][C++]

문제 링크

---

1. 문제 풀이

$n$ 이 최대 $2^{63} - 1$ 일 때, $q^2 \ge n$ 을 만족하는 가장 작은 자연수 $q$ 를 찾는 문제로 이분 탐색 + 매개 변수 탐색을 활용하면 해결할 수 있다. $q$ 는 $0$ 이상 $n$ 의 제곱근 $+1$ 사이에 존재하므로 해당 구간에 대한 Lower Bound 이분 탐색을 적용했다.($2^{63}$ 수준에서도 제곱근 함수의 오차는 매우 작다.)

---

2. 코드

1. 이분 탐색 + 매개 변수 탐색 [Java]

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long n = Long.parseLong(br.readLine());

        System.out.println(lowerBound(n));
    }

    static long lowerBound(long key) {
        long left = 0;
        long right = (long) Math.sqrt(Long.MAX_VALUE) + 1;

        while (left < right) {
            long mid = (left + right) / 2;

            if (mid * mid < key) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right;
    }
}

2. 이분 탐색 + 매개 변수 탐색 [C++]

#include <bits/stdc++.h>
using namespace std;

long long lower_bound_param(long long key) {
    long long left = 0;
    long long right = sqrt(LLONG_MAX) + 1;

    while (left < right) {
        long long mid = (left + right) / 2;

        if (mid * mid < key) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return right;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    cin >> n;
    cout << lower_bound_param(n);
}

---

3. 풀이 정보

1. 이분 탐색 + 매개 변수 탐색 [Java]

언어	시간	메모리	코드 길이
Java 11	96 ms	14320 KB	654 B

2. 이분 탐색 + 매개 변수 탐색 [C++]

언어	시간	메모리	코드 길이
C++ 17	0 ms	2020 KB	507 B

---