백준 17425번. 약수의 합 (Python / 파이썬)

문제

두 자연수 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)을 구해보자.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 둘째 줄부터 테스트 케이스가 한 줄에 하나씩 주어지며 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

각각의 테스트 케이스마다, 한 줄에 하나씩 g(N)를 출력한다.

---

문제 풀이

약수의 합 문제는 약수의 합 2 문제와 비슷한 문제입니다.

약수의 합 2 문제에서 테스트 케이스가 

여러개로 늘어났다는 차이밖에 없습니다.

 

약수의 합 2 문제의 풀이를 동일하게 적용해 

여러 테스트 케이스로 돌리도록 

코드를 작성하였는데 시간 초과 판정을 받았습니다.

 

따라서, DP를 이용해 문제를 해결해보았습니다.

DP list를 만들어준 뒤

1부터 차례대로 해당 수의 배수들에 해당 수를 더해주었습니다.

왜냐하면 해당 수의 배수들은 해당 수를 약수로 포함하기 때문입니다.

예를 들어, 

3의 배수 3, 6, 9, 12, 15는 3을 약수로 포함하기 때문에

해당 index의 배열에 3을 더해준 것입니다.

 

만약 배수들에 수를 더해주었다면, 다음 수로 넘어갈 때

이미 이전 수 까지의 약수 합은 구한 것이므로

이전 index의 dp list 값을 더해주어 누적 합을 구해주었습니다.

 

이렇게 했는데도 시간초과 판정이 나서 결국 PyPy3으로 코드를 제출했습니다ㅠㅠ

---

My Code

import sys
input = sys.stdin.readline

dp = [0] * 1000001 # 약수의 합을 저장할 list

for i in range(1, 1000001):
    for j in range(i, 1000001, i):
        dp[j] += i # 배수들에 i를 더해줌 (i를 약수로 가지므로)
    dp[i] += dp[i - 1] # 이전단계까지 구한 합을 더해 누적 합 계산

for tc in range(int(input())): # 테스트 케이스 개수만큼 반복
    n = int(input()) # 자연수 n
    print(dp[n])