boj13706 제곱근_ java

링크

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

문제

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

입력

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

출력

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

나의 풀이

• 800 자리라는 입력이 너무 부담스럽다... 단순히 long 이나 int를 쓴다고 해결되는 문제가 아닌 것 같다 우선 String으로 받아서 처리를 해야할 것 같은데 어떤 식으로 해결할 수 있을지 좀 고민이된다.
• 해결법 : BigInteger의 사용
  • BigInteger를 통해서 받으면 해결이 된다.
  • BigInteger bigInteger = new BigInteger(””);
  • 이런 식의 선언을 할 수 있고, 계산은 아래의 함수를 이용하면 된다.
  • 덧셈(+) : .add()
  • 뺄샘(-) : .subtract()
  • 곱셈(*) : .multiply()
  • 나눗셈(/) : .divide()
  • 나머지(%) : .remainder()
  • 비교 : .comparseTo()
    • -1 : 파라미터 값이 더 큰경우
    • 1 : 파라미터 값이 더 작은 겨우
    • 0 : 파라미터 값이랑 같은경우
    • n.compareTo(N) → 이것의 결과 값이 n-N이라고 생각하면 좀더 이해하기 편할 것 같다.
• 분할정복 알고리즘으로 문제를 해결하였다.
  • n의 제곱값을 N과 비교하여 값을 구하였다.
  • left와 right를 이용해 n과 N값을 비교하여
    • n>N인경우, right = n
      
    • n<N인 경우 left = n
      
    • n=N인 경우 break;
      
  • 해주고, n값은 (left+right)/2 으로 갱신해준다.
  • 위 과정을 반복해주면, 값이 나온다.
• 핵심 코드

  **while(n.compareTo(N)!=0){
              n = left.add(right).divide(BigInteger.TWO);
              if(n.pow(2).compareTo(N)==0){
                  break;
              }else if(n.pow(2).compareTo(N) == 1){
                  right = n;
              }else if(n.pow(2).compareTo(N) == -1){
                  left = n;
              }
          }**

• 전체 코드

  **package Baekjoon.java.silver;
  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.math.BigInteger;
  
  public class boj13706 {
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          BigInteger N = new BigInteger(br.readLine());
          BigInteger left = BigInteger.ONE;
          BigInteger right = N;
          BigInteger n = BigInteger.ONE;
          while(n.compareTo(N)!=0){
              n = left.add(right).divide(BigInteger.TWO);
              if(n.pow(2).compareTo(N)==0){
                  break;
              }else if(n.pow(2).compareTo(N) == 1){
                  right = n;
              }else if(n.pow(2).compareTo(N) == -1){
                  left = n;
              }
          }
  
          System.out.println(n);
      }
  }**

결과