[백준] 17425 : 약수의 합 (pypy)

누적합, 소수 판정, 에라토스테네스의 체 문제

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

 

문제 설명

1 = 1 (1)
2 = 1, 2 (3)
3 = 1, 3 (4)
4 = 1, 2, 4 (7)
5 = 1, 5 (6)
6 = 1, 2, 3, 6 (12)
7 = 1, 7 (8)
8 = 1, 2, 4, 8 (15)
9 = 1, 3, 9 (13)
10 = 1, 2, 5, 10 (18)
11 = 1, 11 (12)
12 = 1, 2, 3, 4, 6, 12 (28)


1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 4 8 15 21 33 41 56 69 87 99 127

 

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 둘째 줄부터 테스트 케이스가 한 줄에 하나씩 주어지며 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

각각의 테스트 케이스마다, 한 줄에 하나씩 g(N)를 출력한다.

 

예를 들자면, g(4) = f(1) + f(2) + f(3) + f(4) = 1의 약수의 합  + 2의 약수의 합 + 3의 약수의 합 + 4의 약수의 합 = 1 + 3 + 4 + 7 = 15

---

접근 방식

문제를 읽어보면 T의 최대 개수는 100,000 그리고, 자연수 N은 1,000,000이다.

T를 돌 때마다 N보다 작거나 같은 모든 자연수들의 약수의 합을 구한다면 무조건 시간초과가 날 것이다.

 

따라서, 1 ~ 자연수 N의 최댓값인 1,000,000의 약수의 합을 저장하는 배열을 만들고, 이를 활용하자.

문제에서 구해야하는 값은 1 ~ 자연수 N까지의 약수의 누적합이므로 DP 배열을 활용하여 문제를 풀자.

---

💡 풀이코드 (성공)

import sys 
t = int(sys.stdin.readline())
MAX = 1000000
devisors = [1] * (MAX + 1) # 약수의 합 
dp = [0] * (MAX + 1) # 약수의 누적합
dp[1] = 1


def sol():
    for i in range(2, MAX + 1):
        j = 1
        while i * j <= MAX:
            devisors[i * j] += i
            j += 1

    for i in range(2, MAX + 1):
        dp[i] = dp[i - 1] + devisors[i]

sol()
for _ in range(t):
    n = int(sys.stdin.readline())
    print(dp[n])

 

0. 시간복잡도 = O(NlogN)

• 아래 코드의 바깥쪽 루프는 O(N), 안쪽 루프는 O(N / i)의 시간 복잡도를 가진다.
• 전체 시간 복잡도는 아래와 같다. 
  이는 조화급수로 로그에 수렴하므로, 전체 시간 복잡도는 O(NlogN)이 된다.
  
  

for i in range(2, MAX + 1):
    j = 1
    while i * j <= MAX:
        devisors[i * j] += i
        j += 1

조화급수란?
조화급수는 다음과 같은 형태의 수열의 합을 말한다.

즉, 1부터 n까지의 각 자연수의 역수를 모두 더한 값이다.

 

1. 초기화

• N의 최댓값을 나타내는 MAX 변수를 만든다. 
• 자연수 x의 약수의 합을 나타내는 divisors 배열을 만든다.
  모든 자연수는 약수 1을 포함하므로 1로 초깃값을 설정해준다.
  (1로 초깃값을 설정해주고, for문을 돌릴 때는 2부터 반복한다면 1에 해당하는 시간(100,000번 할당 연산)을 줄일 수 있음.)
• 자연수 1 ~ x까지의 약수의 누적합을 나타내는 dp 배열을 만든다.
  1의 약수의 누적합은 1이다. 따라서, dp 배열의 초깃값을 지정해준다.

MAX = 1000000
devisors = [1] * (MAX + 1) # 약수의 합 
dp = [0] * (MAX + 1) # 약수의 누적합
dp[1] = 1

 

2. 자연수 x의 약수의 합 계산 (divisors)

배수의 원리를 활용하자.

예를 들어보자면, 만약 i = 2라면 2를 약수로 가지는 수들의 devisors 배열 값을 약수(2)만큼 더해주는 것이다.

2를 약수를 가지는 수 == 2의 배수를 의미한다.

즉, 아래 로직은 while문을 돌며 자연수 x의 배수를 모두 찾아 devisors 배열 값을 약수의 크기만큼 증가시켜주는 것이다.

for i in range(2, MAX + 1):
    j = 1
    while i * j <= MAX:
        devisors[i * j] += i
        j += 1

 

3. 자연수 x까지의 약수의 누적합 계산 (dp)

결론적으로 1 ~ 자연수 x까지의 약수의 누적합을 구해야 한다.

따라서, dp 배열을 활용하여 누적합을 계산해준다.

for i in range(2, MAX + 1):
    dp[i] = dp[i - 1] + devisors[i]

---

특이점

이 문제는 python으로 제출하면 시간초과가 난다.

내 코드가 잘못된 줄 알고, 다른 사람들의 레퍼런스를 찾아봤는데 모두 pypy로 풀어서 성공했다고 한다.

(파이썬으로 성공한 사람은 아무도 없었음 !)

---

참고문헌

https://enhjh.tistory.com/38

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