[백준(python)] 17427번: 약수의 합 2

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)를 출력한다.

풀이 (시간초과 코드)

n = int(input())

allSum = 0
for i in range(1, n+1):
    sum = 0
    for j in range(1, i+1):
        if i % j == 0:
            sum += j
    allSum += sum
print(allSum)

설명 (시간초과 이유)

처음으로 생각한 방법은 정말 생각나는 대로 중첩for문으로 푸는거였다.
그랬더니 시간초과. 위 코드의 시간복잡도는 중첩for문 때문에 O(n^2)이다.
문제에서 자연수 N의 범위를 (1 ≤ N ≤ 1,000,000)이렇게 지정했다.
N이 충분히 큰 상태이기에 O(n^2)는 시간초과임이 분명하다
따라서 O(n)으로 풀어야 한다. for문을 한 번만 돌려서 풀 수 있어야 함.

시간복잡도 O(n) 설명

N이 6라고 가정해보자
1의 약수의 합 -> 1
2의 약수의 합 -> 1 + 2
3의 약수의 합 -> 1 + 3
4의 약수의 합 -> 1 + 2 + 4
5의 약수의 합 -> 1 + 5
6의 약수의 합 -> 1 + 2 + 3 + 6

1은 모든 수의 약수에 포함된다.
2는 2의 배수인 수의 약수에 포함된다
3은 3의 배수인 수의 약수에 포함된다
4, 5, 6 ... 모든 수가 이 규칙에 적용된다.

N이 6일 때
1은 6 번
2는 3번 (6/2)
3은 2번 (6/3)
4는 1번 (6/4)
5는 1번 (6/5)
6은 1번 (6/6)

일반화 해보면

g(N) = 1*(N/1) + 2*(N/2) + 3*(N/3) + ...

풀이 (시간초과 나지 않는 코드)

n = int(input())

sum = 0
for i in range(1, n+1):
        sum += (i*(n//i))
print(sum)