17427 약수의 합2 문제와 매우 유사한 문제이다. 문제에서 요구하는 조건은 다음과 같다.
- f(A) = A의 약수의 합
- g(N) = f(1) + f(2) + ... + f(N)
- N이 주어졌을 때, g(N)을 구하는 문제
- 테스트 케이스의 갯수
약수의 합 2 문제에서 추가된 부분은 마지막 테스트 케이스의 개수이다.
우선 약수의 합 2 문제의 해결과 똑같이 풀면 다음과 같다.
import sys
input=sys.stdin.readline
n = int(input())
for i in range(n):
sum_ = 0
a = int(input())
for j in range(1, a+1):
sum_ += (a//j)*j
print(sum_)
그러나 이 코드는 바로 시간 초과가 뜬다.
그러므로, 다른 방법을 생각해내야한다.😢
바로 배수의 원리를 이용하는 것이다.
1. N =AB로 나타낼 수 있을 때
2. A와 B는 N의 약수이다.
3. N은 A와 B의 배수이다.
예를 들어, N=6을 생각해보자.
6 = 2 * 3이므로 2와 3은 6의 약수이다.
또한 6은 2또는 3의 배수이다.
이런 아이디어를 사용하면 불필요한 연산을 줄일 수 있다. 즉, 약수가 아닌 수는 연산하지 않겠다는 것이다.
N은 N의 약수의 배수로 이루어져있기 때문에 이를 이용하여 DP 배열을 만들 수 있다.
미리 DP 배열을 만들어놓고 그에 맞는 값을 입력받아 출력하면 된다.
이 경우의 시간복잡도는 $O(nlogn)$이다.
# 최대값 설정
MAX=1000000
# DP 1로 초기화
dp = [1]*(MAX+1)
# S: 값 누적 리스트
s = [0]*(MAX+1)
for i in range(2, MAX+1):
j=1
while i*j <= MAX:
# i의 배수에 값 추가
dp[i*j] += i
j += 1
for i in range(1, MAX+1):
# 누적 값 계산
s[i] = s[i-1] + dp[i]
n = int(input())
ans=[]
for _ in range(n):
a=int(input())
ans.append(s[a])
print('\n'.join(map(str, ans))+'\n')
'알고리즘 > 수학' 카테고리의 다른 글
[백준/수학] 1929 소수구하기(Python, 파이썬) (0) | 2021.05.08 |
---|---|
[백준/수학] 1978 소수찾기(Python, 파이썬) (0) | 2021.05.08 |
[백준/수학] 2609 최대공약수와 최소공배수(Python, 파이썬) (0) | 2021.05.08 |
[백준/수학] 17427 약수의 합2(Python, 파이썬) (2) | 2021.05.06 |
[백준/수학] 1037 약수(Python, 파이썬) (0) | 2021.05.06 |