백준 17425 약수의 합 - python

첫 번째 코드(시간 초과)

import sys
input=sys.stdin.readline
def sum_d(a):
    ans=0
    if a == 1:
        return 1
    elif a == 2:
        return 3
    elif a == 3:
        return 4
    else:
        for i in range(1, int(a**0.5)+1):
            if a % i == 0 and i != a//i:
                ans=ans+i+(a//i)
        if a % (a**0.5) == 0:
            ans += int(a**0.5)
        return ans
ans=[0,1,4,8] + [0 for _ in range(1000000)]
for i in range(4, 1000001):
    ans[i]=ans[i-1]+sum_d(i)
T=int(input())
for _ in range(T):
    N=int(input())
    print(ans[N])

두 번째 코드(성공)

import sys
input = sys.stdin.readline
ans=[0 for _ in range(1000001)]
for i in range(1, 1000001):
    for j in range(i, 1000001, i):
        ans[j] += i
    ans[i] += ans[i-1]
T=int(input())
for _ in range(T):
    N=int(input())
    print(ans[N])

처음에는 재귀를 이용해 ans를 채우는 방법으로 했는데 시간 초과가 났습니다.

약수를 구하는 for 문에서 1부터 int(a**0.5)까지 계속 도는 것이 시간 초과의 원인이었던 것 같습니다.

그래서 다른 분들의 답을 참고했습니다.

약수를 구해서 ans를 채우지 않고 ans의 index 값이 1의 배수인 ans 값에 +1을 해주고, 2의 배수인 ans 값에 +2를 해주고, ... , 1000000의 배수인 ans 값에 +1000000을 해주는 방법으로 하니 맞출 수 있었습니다.