[Swift/백준] 코딩 테스트 준비 - 기초 , 약수의 합

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

 

 

약수의 합 공식인 N/i * i 을 하면 시간 초과가 난다.

 

이 문제는 dp로 약수들의 합을 계산해둔 배열과

누적합을 더해둔 배열을 이용해서 해결해야한다.

 

import Foundation

func main(){
    
    // 약수의 합
    var dp = [Int](repeating: 1, count: 1000001)
    // 누적합
    var s = [Int](repeating: 1, count: 1000001)
    
    for i in 2...1000000 {
        var j = 1
        
        while i*j <= 1000000 {
            dp[i*j] += i
            j += 1
        }
    }
    
    for i in 2...1000000 {
        s[i] = s[i-1] + dp[i]
    }
    
    
    let N = Int(readLine()!)!
    
    for _ in 0..<N {
        
        let M = Int(readLine()!)!
        
        print(s[M])

    }
 
}

main()