_17425 - 약수의 합

까먹을까봐 적어놓는 글.

하따마... 시간초과가 계속 뜬다?!
약수의 합2 과 같은 알고리즘으로 접근했는데 당최 어딜 어떻게 줄이는지 모르겠다.

기본 알고리즘

    func sol(_ N: Int) -> Int {
        var sum = 0
        for i in 1..<N + 1 {
            sum += (N / i) * i
        }
        return sum
    }

N = 5 일때

이렇게 돌아가는 것이다.

1try

    func sol() {
        guard let tc = Int(readLine()!) else { return }
        var numbers = [Int]()
        for _ in 0..<tc {
            let num = Int(readLine()!)!
            numbers.append(num)
        }
        
        for num in numbers {
            var sum = 0
            for i in 1..<num + 1 {
                sum += (num / i) * i
            }
            print(sum)
        }

    }

시간초과!

Solution

미리 계산하는 방법으로 풀어야한다...

    func sol() {
        var dp = Array(repeating: 1, count: 1000001) //각자 약수의 합을 저장
        var sum = Array(repeating: 1, count: 1000001) //누적 약수의 합을 저장
        for i in 2...1000000 {
            var j = 1
            while i*j <= 1000000 {
                dp[i * j] += i
                j += 1
            }
        }

        for j in 2...1000000 {
            sum[j] = sum[j - 1] + dp[j]
        }

        let T = Int(readLine()!)!
        for _ in 1...T {
            let n = Int(readLine()!)!
            print(sum[n])
        }
    
    }

참고 : https://sapjilkingios.tistory.com/entry/Swift-%EB%B0%B1%EC%A4%80-17425%EB%B2%88-%EC%95%BD%EC%88%98%EC%9D%98-%ED%95%A9