[JAVA] 백준 2417번- 정수 제곱근

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

2417번: 정수 제곱근

 

제곱한 숫자가 n보다 큰 수 중에 최솟값을 구하는 문제다.

두가지의 방법으로 풀어볼 수 있다.

 

 

1.Math.sqrt

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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());
        long q = (long)Math.sqrt(n);

        if((q*q) < n) q++;

        System.out.println(q);
    }
}

 

처음에 떠오른 풀이방법은 이 방법이다.

Math.sqrt 메서드로 n의 제곱근 q를 구한다.

q를 제곱한 값이 n보다 작으면 q를 1증가하여 출력하고, n과 같으면 그대로 출력한다. 

 

 

2. 이분탐색 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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(bSearch(n));
    }

    static long bSearch(long n){
        long start = 0;
        long end = n;
        long result=0;

        while(start<=end) {
            long mid = (start + end) / 2;
            if(n<=(long) Math.pow(mid, 2)){
                result=mid;
                end=mid-1;
            }else{
                start=mid+1;
            }
        }
        return result;
    }
}

 

애초에 이분탐색 문제를 풀기위해 이문제를 골랐기 때문에, 이분탐색으로도 풀려고 시도했다.

0부터 n사이의 중간값 mid를 구하고, 이 mid를 제곱시킨 값과 n을 비교한다.

mid의 제곱이 n보다 같거나 클 때의 mid를 구하는데 그 중 가장 작은 값을 구하기 위해 이분탐색을 통해 계속 범위를 좁혀나간다.