백준 17452 약수의합 파이썬(python)

문제: https://www.acmicpc.net/problem/17425

17425번: 약수의 합

풀이:

2022.01.13 - [Python 코딩테스트] - 수학: 백준 17427 약수의 합 2 파이썬(python)

수학: 백준 17427 약수의 합 2 파이썬(python)

 

위 '약수의 합 2' 문제보다 더 빠른 알고리즘을 사용해야 하는 문제입니다. 테스트 케이스가 하나였던 '약수의 합 2'와는 달리 이 문제는 여러 줄의 테스트 케이스가 주어지기 때문입니다.

 

약수의 합을 더 빠르게 구할 수 있는 알고리즘은 바로 입력 받은 수 N은 곧 N의 약수들의 배수라는 것을 이용하는 것입니다. (N = N의 약수들의 배수 ) 

dp(다이나믹프로그래밍) 문제를 풀 때와 같이 미리 약수의 누적합들을 구하고 입력받은 수에 해당하는 누적합을 출력하는 방식으로 풀었습니다.

 

** Pypy3로 제출해야 정답인정이 됩니다. python3로 제출하면 시간 초과가 발생합니다. 

 

정답:

MAX = 1000000

dp = [1] * (MAX+1)
s = [0] * (MAX+1)

# 입력 받은 수 N은 곧 N의 약수들의 배수라는 것을 이용해
# dp 배열을 채운다. dp 배열에는 각 자연수의 약수의 합이 저장된다.  
for i in range(2,MAX+1):
    j = 1
    while i*j <= MAX:
        dp[i*j] += i
        j+=1

# dp 배열엔 약수의 합들이 저장되고 s 배열에는 누적합을 저장 
for i in range(1,MAX+1):
    s[i] = s[i-1] + dp[i]

n = int(input())
ans = []

for _ in range(n):
    tmp = int(input())
    ans.append(s[tmp])
    
print('\n'.join(map(str,ans)))