[백준] 13706. 제곱근 (Java)

 

13706번: 제곱근

 

 

이분탐색 문제. 그런데 이제 범위가 큰...

N의 길이는 800자리를 넘지 않는다

문제에 명시된 N의 범위가 어마무시하기 때문에 무조건 String으로 처리해줘야 하지만

다행스럽게도 Java에는 범위가 infinite한 BigInteger라는 class가 존재한다.

 

 

(공식문서 참조)

BigInteger (Java SE 11 & JDK 11 )

java.math.BigInteger를 import 해줘야 한다.

 

사용법은 간단하다. 괄호 안에 String형태로 수를 넣어주면 되고,

0, 1, 2, 10은 자주 쓰이나 본지 상수로도 정의되어 있다.

 

BigInteger num1 = new BigInteger("1");
// BigInteger num1= BigInteger.ONE;

 

사칙연산은 정직하게 영어 그대로 구현되어 있다. - add(), subtract(), multiply(), divide()

 

두 수의 비교시 num1.compareTo(num2)를 사용하며 결과는 int이다.

• 0: num1 = num2
• 1: num1 > num2
• -1: num1 < num2

 

이제 BigInteger를 이용하여 평소에 구현하던 이분탐색을 짜주면 끝나는 문제이다.

 

코드

import java.io.*;
import java.math.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        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"));

            int result = (mid.multiply(mid)).compareTo(N);
            if (result == 0) break;
            else if (result == 1) end = mid.subtract(new BigInteger("1"));
            else start = mid.add(new BigInteger("1"));
        }
        
        bw.write(mid.toString());
        br.close();
        bw.close();
    }
}

 

그러나 Python으로 풀면 아주 사기적인 풀이가 탄생한다.

 

숫자범위는 메모리가 허락하는 한 가능하다고 한다. (??!?!)

따라서 숫자를 입력받은 후 그냥 제곱근을 씌워버리면 답이 탄생한다... 허헣

 

물론 이렇게 풀면 실력이 늘지 않으니 (ㅎㅎ;) 정공법인 이분탐색으로 하는 것을 추천하는 바이다.

 

Python 3에선 long int나 int나 같은 int이다.

 

여기서 그냥 sqrt와 isqrt가 있는데 isqrt는 앞에 붙은 i로 유추할 수 있듯이 정수형 (integer) 제곱근을 반환해주는 함수이다.

 

코드

import math

N = int(input())

print(math.isqrt(N))

 

 

실행 결과