[Python] 백준 17425번: 약수의 합 (파이썬,수학,정수론)

문제 출처:

https://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의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.

자연수 N이 주어졌을 때, g(N)을 구해보자.

 

입력

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

출력

첫째 줄에 g(N)를 출력한다.

풀이 방법

※사전작업

전에 작성했던 약수의합 2(17427번, https://yoon-e.tistory.com/5) 과 매우 유사한 문제이다.

정확히는 문제에서 구하고자 하는 바는 완전히 같다. 결국 약수와 배수와의 관계를 어떻게 정의할지를 생각해 보라는 것.

달라진것은 단 하나뿐이다. 한 줄씩 입력하는 것이 아닌 반복할 횟수를 정해주고, 그 횟수만큼 g(N)을 구해야한다는 부분이다. 이렇게만 보면 단순히 for loop 를 한번 더 돌리면 해결될 것 같아 보인다. 하지만 정말로 그럴까? 

while True:
    try:
        n = input()
    except:
        break

    n = int(n)  
	for i in range(0,n):
		x = int(input())
    	sol = 0
    	for j in range(1, x+1):
        	sol  = sol+ ((x//i)*j)

    	print(sol)

17427번에서 작성한 코드에 단순 반복문만 포함된 코드이다. 이렇게만 보아도 정답을 구하는데는 큰 문제가 없을 것이다.

하지만 이 코드를 제출하면 "시간초과"로 오답처리가 된다. 무슨 이유일까?

 

이유는 크게 두 가지 이다. 우선, 입력 데이터를 받아오는 방식에서 차이가 발생한다. Python에서 입력데이터를 받아오는 방법은 여러가지가 있지만, 위 코드에서 작성한 방법은 sys 라이브러리를 활용한 데이터 입출력보다 더 시간이 오래 걸린다(입출력 방식에 대한 내용은 추후 포스팅하도록 하겠다). 테스트 케이스가 몇십, 몇백개 정도라면 문제될 것이 없지만 위 문제처럼 10만개정도의 데이터가 입력된다면 이 부분에서 시간 초과 문제가 발생할 수도 있다.

 

두번째 문제는 시간복잡도 이다. 앞의 포스팅에서도 설명했듯이 백준 알고리즘의 경우 시간복잡도가 O(n^2)일땐 2000이상의 테스트케이스가 입력되면 시간초과로 오답처리를 내버린다. 그래서 우린 17427번에서 시간복잡도가 O(n)인 방식으로 약수의합을 구하는 방법을 통해 문제를 해결했다. 문제는 이 17425번에서 테스트케이스를 통한 입력을 받기 위해 for loop를 한번 더 실행하게 되면서 시간복잡도가 O(n^2)로 늘어나버린 문제가 발생했다. 

이해하기 쉽게 예를 들자면, 만약 10만개의 테스트 케이스가 입력되고, 그 케이스들 각각에 100만이 입력된다면, 최악의 경우 100,000 x 1,000,000 번의 루프가 돌게 된다는 것이다.

 

※풀이

그렇다면 이 문제를 해결하는 방법은 무엇일까? 바로 불필요하게 반복되는 경우를 줄이고 미리 모든 f(n)을 저장해두는 것이다. 그렇게 된다면 설사 10만번의 테스트케이스에서 모두 100만이 입력된다고 해도 매번 같은 계산을 중복할 필요가 없어진다.

다음은 모든 f(n)을 어떻게 저장해놓을 것인지에 대해 생각해보자. 여기서 우린 17427번에서 썼던 표를 다시 한 번 떠올려 보아야한다. 

	1	2	3	4	5	6	7	8
1	o	o	o	o	o	o	o	o
2		o		o		o		o
3			o			o
4				o				o
5					o
6						o
7							o
8								o
f(N)	1	3	4	7	6	12	8	15

 

g(N)

1

4

8

15

21

33

41

56

g(N)은 결국 f(N)과 f(N-1)의 합인것을 알 수 있다. 그렇다면 1,000,000까지의 f(N)을 모두 구하기만 하면 문제 해결이란 것이다! 

f(N)은 N의 모든 약수의 합이다. 약수의 합을 구하는 방식은 매우 다양한 방법이 있을것이다. 단순히 N까지 모든 숫자에 대해 약수를 구할수도 있겠지만, 그렇게 되면 결국 시간복잡도는 O(n^2)이 되어버린다. 표를 자세히 보면 좀 더 세련된 방법을 생각할 수 있을 것이다.

 

약수의 관점에서 보자면, 모든 자연수는 약수와 그 배수의 곱으로 이루어진다. 즉 N의 약수가 아니라면 반복문에서 고려해줄 필요가 없다는 뜻이다. 예를 들면 10까지 경우의 수를 보면, 2는 2~10까지 모든 수에 대해 고려해줄 필요가 없다. 2의 배수인 2,4,6,8,10. 5개의 케이스만 고려해주면 되는 것이다. 이렇게 되면 시간복잡도를 O(n^2)에서 O(nlogn)까지 줄일 수 있다.

이야기가 길어졌지만 결국 여기까지 왔다면 코드 구현 자체는 간단하다.

import sys

MAX = 1000000

savechartTemp = [1]*(MAX+1)
savechartReal = [0]*(MAX+1)
savechartReal[1] = 1


for i in range(2,(MAX+1)):
    for j in range(1,(MAX//i)+1):
        savechartTemp[j*i] = savechartTemp[j*i] + i

    savechartReal[i] = savechartReal[i-1] + savechartTemp[i]

x = int(sys.stdin.readline())
data = [sys.stdin.readline().strip() for i in range(x)]

for i in data:
    n = int(i)
    print(savechartReal[n])

 

참고)

문제 풀이와는 별개로, Python3로 제출하게 되면 시간초과로 오답처리가 된다. 다만 같은 코드를 PyPy로 돌리면 정답처리가 되는데, 이는 PyPy가 Python3 보다 더 빠른 연산속도를 가지기 때문에 그런것이므로 만약 다른 문제에서도 Python3로 시간초과가 뜬다면 PyPy로 제출하는 방법도 생각해보자