[백준] 2417 정수 제곱근 - 이분탐색(binary search) JAVA

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

코드설명

이분탐색을 활용하여 해결합니다.

 

1부터 N까지의 숫자들을 이분탐색으로 순회하면서 해당 middle에 있는 값의 제곱이 N보다 크거나 같으면, end = middle - 1 처리를 통해 값을 줄여주면서 middle 값의 제곱이 N보다 크거나 같게 해주는 가장 최소한의 수를 찾아줍니다.

 

이 과정에서 N보다 크거나 같은 최소한의 수를 찾기 위해 

먼저 >= N 처리를 해주어야만, end가 middle - 1 처리로 어들면서 최소한의 수를 찾을 수 있습니다.

if( Math.pow(middle, 2) >= N ) {
    answer = middle;
    end = middle - 1;
} else  {
    start = middle + 1;
}

 

 

Math.sqrt로 N의 제곱근을 구한뒤, N보다 작다면 + 1, 같거나 크다면 그대로 출력해도 됩니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	public static long N, M, K = 0;
	public static long answer = 0;
	public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Long.parseLong(st.nextToken());
    	
    	binarySearch(0, N);
    	
    	System.out.println(answer);
    }
    
    public static void binarySearch(long start, long end) {
    	long left = 0;
    	long right = end;
    	
    	while(left <= right) {
    		long middle = (left + right) / 2;
    		if( Math.pow( middle, 2) >= N) {
    			answer = middle;
    			right = middle - 1;
    		}
    		else if(Math.pow(middle, 2) < N){
    			left = middle + 1;
    		}
    	}
    	
    }
    
}

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
 
public class Main {
	
	public static long N;
	public static long answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Long.parseLong(st.nextToken());
    	
    	binarySearch();
    	System.out.println(answer);
    }
    
    public static void binarySearch() {
    	long start = 0;
    	long end = N;
    	
    	while(start <= end) {
    		long middle = ( start + end ) / 2;
    		    		
    		if( Math.pow(middle, 2) >= N ) {
    			answer = middle;
    			end = middle - 1;
    		} else  {
    			start = middle + 1;
    		}
    	}
    }
 
}