[백준_2417번] 정수 제곱근

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

2417번: 정수 제곱근

[문제]

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

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_2417 {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		long n=sc.nextLong();
		
		long start=0;
		long end=n;
		long min=Long.MAX_VALUE;
		
		/*
		 * 이진탐색을 사용하려 long 자료형을 제곱했을 때 
		 * n보다 큰 값중 제일 작은 값을 찾는 문제
		 */
		while(start<=end) {
			long mid=(start+end)/2;
			long result=(long) Math.pow(mid, 2); // 제곱
			
			/*
			 * mid를 제곱한 값 중 n보다 크지만 
			 * 가장 작은 값을 찾는것이기 때문에
			 * 제곱값이 n보다 큰 경우 min에 mid 값을 저장하고, 
			 * end의 범위를 줄여 재탐색한다.
			 */
			if(result>=n) {
				min=mid;
				end=mid-1;
			}
			// 제곱값이 n보다 작은 경우 start 범위를 키워 재탐색한다.
			else 
				start=mid+1;
		}
		
		System.out.println(min);
	}

}

 

[고찰]

 이번 문제의 출력 조건은 q^2 ≥ n인 가장 작은 음이 아닌 정수 q를 출력하는 것이다. 주어지는 n의 범위가 굉장히 크기 때문에 이진탐색을 사용하여 구할 수 있다.

 long 자료형을 제곱한 값이 n보다 크지만 가장 작은 값을 찾아야하기 때문에 제곱값이 n보다 큰 경우 mid 값을 따로 저장 후, end 범위를 줄여 재탐색한다. 반대의 경우에는 start 범위를 키워 재탐색해 해결할 수 있다.