[Python] 백준 17425 - 약수의 합

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

 

문제

두 자연수 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)를 출력한다.

---

풀이

17427번 풀이를 그대로 넣으면 1,000,000 * 100,000 번 연산을 해야하므로 당연히 시간 초과가 난다.

따라서 여기서는 에라토스테네스의 체 아이디어를 적용해서 누적합을 이용해서 풀어주어야 한다.

 

먼저 누적합을 저장할 리스트를 만든다.

그리고 소수판정하듯이(소수판정은 아님), 1부터 시작해서

1의 배수 칸에 1을 더해주고,

2의 배수 칸에 2를 더해주고,

3의 배수 칸에 3을 더해주고....

 

이렇게 반복하면 dp에 저장된 값이 구하고자 하는 값이 된다.

 

dp = [0]*1000001
for i in range(1, 1000001):
    for j in range(i, 1000001, i):
        dp[j] += i
    dp[i] += dp[i-1]
T = int(input())
for i in range(T):
    N = int(input())
    print(dp[N])

 

근데 이렇게 하면 될 것 같지만 시간초과가 난다. C로 푼 사람들은 여기까지만 해도 될 것 같은데, 이 문제에 제한시간에 추가시간이 없고 무조건 1초여서 파이썬은 약간의 최적화를 해줘야 한다.

 

T = int(input())
order = []
for i in range(T):
    N = int(input())
    order.append(N)
M = max(order)

dp = [0]*(M+1)
for i in range(1, M+1):
    for j in range(i, M+1, i):
        dp[j] += i
    dp[i] += dp[i-1]

for i in order:
    print(dp[i])

 

누적합 계산을 1,000,000까지 하는게 아니라 쿼리 중 가장 큰 값으로 하는 것이다(의미가 있나????테스트케이스에 큰 값이 없는 듯)