[자바, 파이썬] 백준 13706 - 제곱근 (boj java)

문제 : boj13706

 

 

  단순히 제곱근(루트)을 구하는 간단한 문제긴한데, 문제는 정수의 자리수가 최대 800자리나 된다는 점이다. 따라서 큰 수 연산이 필요하다.

 

  파이썬의 경우엔 애초에 무한정 크기의 숫자 표현이 가능하다. 다만 단순히 int(input())**0.5 와 같은 코드로는 불가능한데, 너무 큰 수에대해서는 **0.5가 사용 불가하다고 한다. 찾아보니 math에 isqrt 라는 함수가 있어서 그걸 사용했다.

 

  자바의 경우엔 우선 큰 수의 경우엔 BigInteger로 표현 가능하다. 그리고 BigInteger에 sqrt라는 함수가 있으므로 해당 함수를 사용하면 되는데, 문제는 이게 자바 9에서 추가되었다. 따라서 자바9 이상에서는 간단하다. 자바 8 이하에서 짤려면 비트 연산을 활용해서 직접 제곱근을 구해줘야 한다. 그러니 자바9 이상으로 제출하면 된다! 굳이 짜고싶다면 자바8 코드의  sqrt 함수를 참고해보자.

 

 

코드 (자바8) : github

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

public class Main {
    private BigInteger sqrt(BigInteger bi) {
        BigInteger div = BigInteger.ZERO.setBit(bi.bitLength()/2);
        BigInteger div2 = div;
        while(true) {
            BigInteger tmp = div.add(bi.divide(div)).shiftRight(1);
            if (tmp.equals(div) || tmp.equals(div2))
                return tmp;
            div2 = div;
            div = tmp;
        }
    }
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BigInteger bi = new BigInteger(br.readLine());
        System.out.println(sqrt(bi));
    }
    public static void main(String[] args) throws Exception{
        new Main().solution();
    }
}

 

 

코드 (자바9 이상) : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BigInteger bi = new BigInteger(br.readLine());
        System.out.println(bi.sqrt());
    }
    public static void main(String[] args) throws Exception{
        new Main().solution();
    }
}

 

 

코드 (파이썬) : github

from math import isqrt
print(isqrt(int(input())))