[ 수학 ] 백준 17427 약수의 합 2 kotlin

문제 링크

17427번: 약수의 합 2

 

💡문제 분석 요약

• 자연수 A의 약수의 합은 f(A)이다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)이다. 자연수 N이 주어졌을 때, g(N)을 구해야한다.
• 1부터 N까지 각 숫자에 대하여 그 숫자의 모든 약수들의 합을 구해야 한다.
• n 의 상한(0 < n < 1,000,000)이 크기 때문에 시간 및 공간 복잡도 모두 최적화하는 것이 필요하다.

 

💡알고리즘 설계

약수합을 최적으로 구하는 알고리즘이 필요하다. 

• 에라토스테네스의 체와 비슷한 방법을 사용하여, 각 숫자의 약수들의 합을 효율적으로 계산한다.
• 1부터 N까지 각 숫자에 대하여 그 숫자의 모든 약수들의 합을 구하고, 이를 배열에 저장한다.
• 배열에 저장된 약수들의 합을 모두 더하여 g(N)을 구한다.

*에라토스테네스의 체 는 소수를 구하는 가장 오래되고 대표적인 알고리즘 이다.

💡코드

fun main() {
    val br = System.`in`.bufferedReader()
    val N = br.readLine().toInt()
    val g = LongArray(N + 1) { 1L } // 모든 숫자는 자기 자신을 약수로 갖기 때문에 1로 초기화

    // 에라토스테네스의 체 비슷한 방법으로 각 숫자의 약수들의 합 계산
    for (i in 2..N) {
        var j = i
        while (j <= N) {
            g[j] += i.toLong()
            j += i
        }
    }

    // 누적합 계산
    for (i in 2..N) {
        g[i] += g[i - 1]
    }

    println(g[N])
}

 

 

💡시간복잡도

알고리즘의 시간 복잡도는 O(N log N)이다. 각 숫자의 약수를 찾는 과정에서 모든 약수들을 찾기 때문에, N까지의 모든 숫자에 대해 약수들의 합을 계산하는 과정이 N log N 번의 연산을 수행하기 때문이다..

 

💡 틀린 이유

이번 문제는 수학을 풀이하는 문제였는데, 약수의 합을 구하는 알고리즘을 내가 작성하지 못했다. 다양한 수학적인 부분을 알고리즘으로 구현하는 연습이 필요할 것 같다.

  

💡 다른 풀이

풀이는 크게 현재 작성한 풀이와, 또 다른 풀이가 존재했다.  직접 많은 숫자를 확인하며 찾은 규칙을 활용한 것인데, 해당 방법이 복잡도 측면에서 훨씬 큰 이점이 있는 방법이었다.(O(N))

 

10을 기준으로 한다면,

1 은 총 10번 등장하고 ((10 / 1) * 1),

2 는 총 5번 등장하고 ((10 / 2) * 2),

3 은 총 3번 등장하고 ((10 / 3) * 3),

4, 5 는 총 2번 등장하고 ((n (10) / i ( 4 ~ 5 )) * i ( 4 ~ 5 )),

6, 7, 8, 9, 10 은 총 1번 등장한다 ((n (10) / i ( 6 ~ 10 )) * i ( 6 ~ 10 )) 

 

이를 수식으로 정리하면,  n / i ) * i 가 되며, 이를 활용한 방법이다.

 

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    var answer = 0L
    for (i in 1..n) {
        answer += (n / i) * i
    }
    println(answer)
}

 

 

 

 

💡 느낀점 or 기억할정보

 

현재 다양한 문제유형을 풀이를해보고 있는데, 다방면으로 많이 부족함을 느끼고 있다. 그리디 문제를 풀이할 땐, 코딩 피지컬의 부족함을 느꼈는데,  이번 수학과 관련해서도 코딩 피지컬의 부족으로 인한 문제 + 수학 공식의 부족을 인지할 수 있었다.

 

수학 공식의 경우, 다방면으로 활용이 될 수 있으므로, 카테고리화 하여 정리해놓고, 복습하며 다른 알고리즘 문제를 풀이할 때 응용할 수 있도록 해야겠다.

 

• 알고리즘 별 카테고리화 정리 진행