백준 boj 17425 - 약수의 합 (파이썬, python)

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

17425번: 약수의 합

 

약수의 합2와 이어지는 문제인듯 했으나, 그렇지 않았다.

 

https://liltdevs.tistory.com/49?category=1054462 

백준 boj 17427 - 약수의 합 2 (파이썬, python)

 

위의 문제에서는 약수의 개수에 대한 컨셉을 통해 풀어내었지만,

같은 방식으로 문제를 풀어내었더니 시간초과에 걸렸다...

하여, 이번에는 배수의 컨셉을 활용하였다.

 

주어지는 지문에는 A = BC 라고 되어있고,

이것은 6 = 2*3 으로 해석할 수 있다.

 

위의 개념을 차용하여 다이나믹 프로그래밍과 에라토스테네스의 체를 활용하여

어떤 수에 대해 배수로 그 수를 표현할 수 있는 수라면,

어떤 수에 해당하는 배열의 index에 그 수를 더해줬다.

 

즉 6일 때 2와 3을 더해 약수의 합들이 들어있는 배열 하나,

그리고 이전까지의 약수들의 합이 들어있는 배열 하나를 생성하였다.

 

code

MAX = 1000000
dp = [1] * (MAX + 1)
sum = [0] * (MAX + 1)

for i in range(2, MAX + 1):
    j = 1
    while i * j <= MAX: # i 의 배수 값을 MAX 까지 더해줬다.
        dp[i * j] += i # i가 2라면 dp[2], dp[4], dp[6], dp[8] ... 에 2가 더해진다.
        j += 1
for i in range(1, MAX + 1):
    sum[i] = sum[i - 1] + dp[i] # 구해진 dp를 활용해 쭉 더해준다.

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