문제를 읽어보면 T의 최대 개수는 100,000 그리고, 자연수 N은 1,000,000이다.
T를 돌 때마다 N보다 작거나 같은 모든 자연수들의 약수의 합을 구한다면 무조건 시간초과가 날 것이다.
따라서, 1 ~ 자연수 N의 최댓값인 1,000,000의 약수의 합을 저장하는 배열을 만들고, 이를 활용하자.
문제에서 구해야하는 값은 1 ~ 자연수 N까지의 약수의 누적합이므로 DP 배열을 활용하여 문제를 풀자.
💡풀이코드 (성공)
import sys
t = int(sys.stdin.readline())
MAX = 1000000
devisors = [1] * (MAX + 1) # 약수의 합
dp = [0] * (MAX + 1) # 약수의 누적합
dp[1] = 1
def sol():
for i in range(2, MAX + 1):
j = 1
while i * j <= MAX:
devisors[i * j] += i
j += 1
for i in range(2, MAX + 1):
dp[i] = dp[i - 1] + devisors[i]
sol()
for _ in range(t):
n = int(sys.stdin.readline())
print(dp[n])
0. 시간복잡도 = O(NlogN)
아래 코드의 바깥쪽 루프는 O(N), 안쪽 루프는 O(N / i)의 시간 복잡도를 가진다.
전체 시간 복잡도는 아래와 같다. 이는 조화급수로 로그에 수렴하므로, 전체 시간 복잡도는 O(NlogN)이 된다.
for i in range(2, MAX + 1):
j = 1
while i * j <= MAX:
devisors[i * j] += i
j += 1
조화급수란? 조화급수는 다음과 같은 형태의 수열의 합을 말한다. 즉, 1부터 n까지의 각 자연수의 역수를 모두 더한 값이다.
1. 초기화
N의 최댓값을 나타내는 MAX 변수를 만든다.
자연수 x의 약수의 합을 나타내는 divisors 배열을 만든다. 모든 자연수는 약수 1을 포함하므로 1로 초깃값을 설정해준다. (1로 초깃값을 설정해주고, for문을 돌릴 때는 2부터 반복한다면 1에 해당하는 시간(100,000번 할당 연산)을 줄일 수 있음.)
자연수 1 ~ x까지의 약수의 누적합을 나타내는 dp 배열을 만든다. 1의 약수의 누적합은 1이다. 따라서, dp 배열의 초깃값을 지정해준다.
