🎈문제 내용
17427 약수의 합 2
두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.
자연수 N이 주어졌을 때, g(N)을 구해보자.
입력
첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
출력
첫째 줄에 g(N)을 출력한다.
제한
시간 - 0.5초
메모리 - 512MB
🎈풀이
n = int(input())
sum = 0
for i in range(1, n + 1):
sum += (n//i) * i
print(sum)이 문제는 시간복잡도 O(N)을 구하는 문제로,
기존 약수 구하는 방식으로 문제를 풀게 되면 시간초과가 발생하게 된다.
해당 시간초과를 해결하기 위해 약수를 배수 방식으로 풀어나가는게 좋다.
예를들어 n=4 일때,
1 -> 1부터 4까지 모두 약수로 들어가고,
2 -> 2와 4
3 -> 3
4 -> 4
이므로, 1은 4번, 2는 2번, 3과4는 각각 한번 들어가는 것을 알 수 있다.
이와 같이 i가 n//i한 갯수만큼 가지고 있게 되는 것이다.
그 결과로 sum += (n//i) * i 라는 결과가 나오게 된다.
