백준]17427 약수의 합2

17427 약수의 합2

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

패턴 찾다

약수의 합을 나열

1 → 1

2 → 1 + 2

3 → 1 + 3

4 → 1 + 2 + 4

5 → 1 + 5

6 → 1 + 2 + 3 + 6

7 → 1 + 7

8 → 1 + 2 + 4 + 8

9 → 1 + 3 + 9

10 → 1 + 2 + 5 + 10

• n 의 배수에 해당 되는 수는 n 값이 무조건 포함 되어 있다.
  • 10 = 1 , 2, 5, 10
    • 1의 배수
    • 2의 배수
    • 5의 배수
    • 10의 배수

배열을 미리 생성해 두고 배열의 index을 해당 수의 총합 값을 저장 한다.

예 [10] = 1 + 2 + 5 + 10

그럼 이러한 형태로 저장 되게 된다.

Index : 0	1	2	3	4	5
Value : 0	1	3	4	7	6

그리고, 입력한 수 이하의 모든 자연수 각각의 약수의 합을 전부 더한 값을 구하는 것

예 : 4 의 총합 = 1 + 3 + 4 + 7 = 15

fun main() {
    val input = readLine()!!.toInt()

    val dp = LongArray(input + 1) { 0 }
    for (i in 1..input) { // 1 ~ input의 배수 만큼 index 값의 약수의 합을 만든다.
        var j = i
        while (j <= input) {
            dp[j] += i.toLong()
            j += i // 각 배수에 해당하는 index에 값을 더한다.
        }
        dp[i] += dp[i-1] // 이전 배열을 가져와 더하면 index 값 이하의 모든 자연수 각각의 약수의 총합이 계산 된다.
    }
    println(dp[input])
}

더욱 더 최적화 된 로직을 찾다

g(6)의 경우

6 이하의 자연수 중 에서 1 을 약수로 갖는 수의 개수 = 6

6 이하의 자연수 중 에서 2 을 약수로 갖는 수의 개수 = 3

6 이하의 자연수 중 에서 3 을 약수로 갖는 수의 개수 = 2

6 이하의 자연수 중 에서 4 을 약수로 갖는 수의 개수 = 1

6 이하의 자연수 중 에서 5 을 약수로 갖는 수의 개수 = 1

6 이하의 자연수 중 에서 6 을 약수로 갖는 수의 개수 = 1

fun main() {
    val input = readLine()!!.toInt()

    var answer = 0L
    for (i in 1..input) {
        answer += (input / i * i).toLong()
    }
    println(answer)
}