[코틀린] 백준 - 약수의 합2

---

 

📌  풀이 1 (시간 초과)

에라토스테네스의 채 방법 사용

에라토스테네스의 채란?

• n의 약수의 합을 구할 때 나누는 수를 1부터 N까지 모두 검사한다면?

// answer에 약수의 개수 저장
var answer = 0
for (i in 0 until N) { 
	if (N % i == 0) answer += i 
}

• 위 식은 시간 복잡도는 O(N)이다.
• 이때 에라토스테네스의 채라는 방법을 이용하면 시간 복잡도가 획기적으로 줄어드는데

합성수는 그 수의 제곱근보다 작거나 같은 약수를 갖는다

• 즉 N까지 검사할 것을 루트 N까지만 검사하면 된다는 것 -> 시간 복잡도를 O(√n) 로 만들어준다.
• 예를 들어 N=10000이라면 10000번 검사할 것을 100번만 검사하면 된다는 것

 

코드

import kotlin.math.*

// for문 시간복잡도 O(N) * calulate() 시간복잡도 O(√n)
// 따라서 시간복잡도 O(N * √N)
fun main() = with(System.`in`.bufferedReader()) {
    val input = readLine()!!.toLong()
    var answer = 0L
    for (i in (1..input)) { 
        answer += calculate(i.toDouble())
    }
    println(answer)
}

// n 의 약수의 합을 구해주는 함수
// 시간 복잡도 O(√n)
fun calculate(n: Double): Long {
    val nInt = n.toLong()
    val sq = sqrt(n)
    val target = floor(sq).toInt()
    var total = 0L
    for (i in (1 ..target)) {
        if (nInt % i == 0L) {
            val temp = (nInt / i)
            total += if (temp == i.toLong()) {
                i.toLong()
            } else {
                i + temp
            }
        }
    }
    return total
}

• 위 코드를 보면 for문 시간복잡도 O(N) * calulate() 시간복잡도 O(√n) 해서 총 시간 복잡도 O(n * √n)가 걸린다. 
• 하지만 이 문제의 N의 범위는 1 ~ 10억까지이고 1억의 연산이 1초가 걸린다는 점을 생각하면 시간 복잡도 O(n * √n)은 대략 10초 정도가 걸리기 때문에 시간 초과가 발생한다.

 

---

 

 

📌  풀이 2

• N이하의 자연수 중에서 1을 약수로 갖는 수의 개수는 가우스(N/1) 개
• N이하의 자연수 중에서 2를 약수로 갖는 수의 개수는 가우스(N/2) 개
• N이하의 자연수 중에서 3을 약수로 갖는 수의 개수는 가우스(N/3) 개

 

 

 

그림 예시

7을 예로 들어 보자.

아래 그림에서 빨간 네모 안에 있는 숫자들의 합이 1부터 7까지의 숫자의 각 약수의 합이다.

네모칸 안의 숫자들이 약수의 총 합

• 7 이하의 자연수 중에서 1을 약수로 갖는 수의 개수는 가우스(7/1) = 7개
• 7 이하의 자연수 중에서 2을 약수로 갖는 수의 개수는 가우스(7/2) = 3.xx의 가우스 = 3개
• 7이하의 자연수 중에서 3을 약수로 갖는 수의 개수는 가우스(7/3) = 2.xx의 가우스 = 2개
• ...

 

방식이다. 위 방법을 사용해서 코드를 짜 보면

 

 

// 시간복잡도 O(N)
fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine()!!.toInt()
    var answer = 0L
    for (i in (1..n)) {
        answer += (n / i) * i // (n / i) -> i의 배수의 개수 즉 i를 약수로 갖는 수
    }
    println(answer)
}

• 코틀린의 ' / ' 가 자동으로 가우스의 역할을 해주므로 간단하게 해결할 수 있다.
• 위 코드는 1부터 N까지의 for문 한 번으로 문제를 해결하므로 시간 복잡도 O(N)으로 문제를 해결할 수 있다.