[백준] S5 13706번 제곱근 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

13706번: 제곱근

[문제] 

정수 N이 주어졌을 때, N의 제곱근을 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 양의 정수 N이 주어진다. 정수 N의 제곱근은 항상 정수이며, N의 길이는 800자리를 넘지 않는다.

[출력]

첫째 줄에 정수 N의 제곱근을 출력한다.

 

 

---

[풀이]

1. 범위를 생각해서 Integer가 아닌 BigInteger를 사용한다.

2. 기존의 이분 탐색을 하듯이 BigInteger를 사용해 이분 탐색을 해준다.

[접근]

1. N의 길이는 800자리를 넘지않는다고 하였는데 이는 그냥 처리할 수 없다.

2. 이를 해결하기 위해 검색을 해 본 결과 BigInteger를 사용해서 문제를 해결할 수 있었다.

3. BigInteger를 사용해 이분 탐색을 하면 문제를 해결할 수 있을 것 같아 이 방법을 사용해 문제를 해결했다.

[코드]

package BOJ_silver;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main_S5_13706 {
	static int result;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		// 범위가 크기때문에 BigInteger를 사용
        BigInteger n = new BigInteger(br.readLine());
        BigInteger start = new BigInteger("1");
        BigInteger end = n;
        BigInteger mid;
 
        while (true) {
            mid = start.add(end);
            mid = mid.divide(new BigInteger("2"));
 
            // mid * mid와  n 비교
            // 같다면 0
            // mid * mid가 크다면 1
            // mid * mid가 작다면 -1
            result = (mid.multiply(mid)).compareTo(n);
            
            // 같다면 종료
            if (result == 0)
            	break;
            // mid * mid가 크다면
            else if (result == 1)
            	// 1을 빼고 연산
            	end = mid.subtract(new BigInteger("1"));
            // mid * mid가 작다면
            else
            	// 1을 더하고 연산
            	start = mid.add(new BigInteger("1"));
        }
        
        System.out.println(mid);
    }
}