함량 100%

함지의 개발일기

알고리즘/수학

[백준/수학] 17425 약수의 합(Python, 파이썬)

Haamjee 2021. 5. 7. 01:12

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')

 

www.acmicpc.net/problem/17425

 

17425번: 약수의 합

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더

www.acmicpc.net