백준 17425번 파이썬 문제풀이(수학 - 약수의 합)

코드

import sys

# 최대값 설정
MAX = 1000000

# 각 인덱스마다 약수의 합을 담아 놓을 배열 초기화
dp = [0] * (MAX + 1)
# 각 인덱스까지 누적합을 담을 배열 초기화
s = [0] * (MAX + 1)

for i in range(1, MAX + 1): #1부터 최대값까지
    j = 1 # i에 곱할 j를 선언
    while i * j <= MAX: # i * j 값이 최대값이 넘지 않을 때까지
        # dp배열의 인덱스인 i의 배수에 i 값을 더해준다. 
        dp[i * j] += i #예를들면 3*j의 해당하는 값들은 3을 무조건 약수로 가지기 때문에 3을 더해준다 
        j += 1 #j값 증가
    s[i] = s[i - 1] + dp[i] #해당 dp[i]의 값 까지 더한 누적합을 s배열에 넣어준다.

t = int(input()) #테스트 케이스 개수 입력

for _ in range(t):
    a = int(sys.stdin.readline())
    sys.stdout.write(str(s[a])+"\n")

 

-> 우선 이문제는 앞선 문제 https://ji-gwang.tistory.com/241

백준 17427번 파이썬 문제풀이(수학 - 약수의 합2)

를 먼저 풀고 보는 것이 좋다. 앞선 식으로 해당문제를 풀게 되면 시간초과가 발생한다. 따라서 해당 문제를 해결하기 위해서는 미리 약수의 합들과 누적합들을 구해놓고 출력할 때는 그 해당값들을 꺼내는 방식으로만 풀어야 한다.