까먹을까봐 적어놓는 글.
하따마... 시간초과가 계속 뜬다?!
약수의 합2 과 같은 알고리즘으로 접근했는데 당최 어딜 어떻게 줄이는지 모르겠다.
func sol(_ N: Int) -> Int {
var sum = 0
for i in 1..<N + 1 {
sum += (N / i) * i
}
return sum
}
N = 5 일때
이렇게 돌아가는 것이다.
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)
}
}
시간초과!
미리 계산하는 방법으로 풀어야한다...
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])
}
}