[Silver V] 제곱근 - 13706 - Kotlin

문제 링크

성능 요약

메모리: 22824 KB, 시간: 272 ms

분류

임의 정밀도 / 큰 수 연산(arbitrary_precision), 이분 탐색(binary_search), 수학(math)

문제 설명

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

입력

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

출력

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

---

풀이

• 제곱근을 이분 탐색으로 구현하려면 먼저 기본적인 이분 탐색 구조를 알고 활용하면 쉽다.

• 내가 찾으려는 숫자가 16이라면 이것을 last 인덱스로 넣고 0~16 사이로 시작하여 찾는 것이다. 조건은 mid가 찾고 있는 제곱근이 맞는지를 확인하면 된다.

• 하지만 이 문제에서 걸림돌은 N의 길이가 무척이나 길게 입력될 수도 있어서 Int로는 눈물을 지으며 틀렸습니다를 봐야한다. 그래서 무한의 정수가 들어올 수 있는 BigInteger라는 것을 활용해 풀 수 있다.

• BigInteger에 대한 설명 글을 참고
  https://coding-factory.tistory.com/604

답

import java.math.BigInteger

fun main() {
    var N :BigInteger = readln().toBigInteger()
    println(cal(N))
}
fun cal(findNum:BigInteger) : BigInteger {
    var first:BigInteger = (0).toBigInteger()
    var last:BigInteger = findNum
    var mid : BigInteger
    while(first <= last) {
        mid = ( first+last ) / (2).toBigInteger()
        mid*mid
        if(mid*mid==findNum) {
            return mid
        }
        else if(mid*mid> findNum) {
            last = mid- (1).toBigInteger()
        }
        else {
             first = mid+(1).toBigInteger()
        }
    }
    return (0).toBigInteger()
}