백준 2417: 정수 제곱근 [JAVA]

[문제 링크]

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

 

[난이도]

- Silver 4

 

[알고리즘]

- 이분 탐색

 

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static long n, answer = 0;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Long.parseLong(br.readLine());
        binarySearch(n);
        System.out.println(answer);
    }

    static void binarySearch(long key) {
        long left = 0;
        long right = key;
        while (left <= right) {
            long mid = (left + right) / 2;
            if (key <= Math.pow(mid, 2)){
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
    }
}

[풀이]

이분탐색 알고리즘 보다 타입맞추는게 더 까다로웠다.

(mid * mid) 로 계산하면 long의 범위를 넘어가 버려 정답을 맞출 수 없다.

Math.pow(mid, 2) 는 반환값이 double 이기때문에 이를 사용해야한다.