백준 2417 정수 제곱급

문제

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

입력

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

출력

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

예제 입력 1 복사

122333444455555

예제 출력 1 복사

11060446

 

풀이

 

단위가 커서 long 자료형을 사용햇고

 

m이 value의 제곱근 이상인 경우는 m이 더 커지면 무조건 value의 제곱근 보다 크니 r을 줄이고

작으면 m보다 작은 값은 절대 value의 제곱근 보다 클 수 없으니 l을 m+1 하면서 이분탐색 했다

import java.awt.*;
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

class Main
{
    static long Solution(long value) {
        long l = 1, r = value, ans = 0;
        while (l <= r) {
            long m = (l + r) / 2;
            // lower bound
            if (m  >= Math.sqrt(value)) {
                r = m - 1;
                ans = m;
            }
            else l = m + 1;
        }
        return ans;
    }


    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);

        long l = in.nextLong();
        System.out.println(Solution(l));
    }
}