[Python] 백준 17427번: 약수의 합2 (파이썬)

문제 출처:

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

17427번: 약수의 합 2

 

문제

두 자연수 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)을 구해보자.

 

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

 

출력

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

풀이 방법

※ 실수하기 좋은 풀이

언뜻 보면 단순해 보이는 문제이다. 주어진 n의 약수를 모두 더한 값을 f(n) 이라고 했을때, 1부터 n까지 모든 정수의 f(i)의 합을 구하라는 것. 문제에서 주어진대로 풀이를 하자면 1)n의 약수를 구하는 함수를 만든다. 2)그 함수를 1부터 n까지 반복한다. 이 두 단계로 답을 구할 수 있다.

아래 코드에서도 볼 수 있듯이, 약수를 구하는 과정만 해결한다면 바로 풀 수 있는 간단한 문제로 보인다.

def divide_num(x):
    summ = 0
    for num in range(1,int(pow(x,1/2))+1):
        #num이 x의 약수라면
        if x%num == 0:
            #num이 x의 제곱근인 경우
            if x//num == num:
                summ = summ + num
            #약수 num 과 대칭되는 약수를 한번에 계산
            else:
                summ = summ + num + x//num
    return summ

while True:
    try:
        n = int(input())

    except:
        break

    sol = 0
    for i in range(1,n+1):
        sol = sol + divide_num(i)

    print(sol)

하지만 이대로 답을 제출하면 어떻게 될까? 

어라? 시간초과로 오답처리가 된다. 분명 정답을 찾는데는 문제가 없는 프로그램인데 왜 오답이 되는것일까?

답은 시간복잡도 O(n) 에 있다. 시간복잡도(Time Complexity)란 문제를 해결하는데 걸리는 시간을 코드의 문자열의 길이에 따라 정량화 시켜 나타낸 것이다. 예를 들면 for loop 가 한번이면 O(n)의 시간복잡도를 가지는 것이다.

 

그렇다면 위의 코드의 시간복잡도는 얼마일까? divide_num()함수에서 중첩되지 않은 단일 for loop를 돌리고 있으니 O(n)의 시간복잡도를 가진다. 그리고 본 함수에서 다른 for loop 안에서 divide_num() 함수를 실행시킨다. 결국 O(n)이 중첩되어 O(n^2)의 시간복잡도를 가지는 것이다. 

 

문제는 백준 알고리즘 문제는 O(n^2)의 시간복잡도를 가지는 코드는 입력값이 2000 전후여야 시간초과가 발생하지 않는다. 하지만 해당 문제의 입력값의 범위는 자연수 N(1 ≤ N ≤ 1,000,000). 즉, 10만단위의 값이 입력되면 시간초과로 오답이 발생한다.

 

 

※ 올바른 풀이

그렇다면 해결방법은 무엇일까? 사실 이 문제는 코드 구현이나 알고리즘 자체보다도 문제를 보는 시각을 약간 뒤집어야하는 방식의 문제이다. 주어진 문제를 정직하게 접근했다간 위의 예시처럼 오답이 발생할 확률이 굉장히 높다.

 

우선 우리는 약수란 무엇인지, 왜 하필이면 1부터 n까지 모든수의 f(n)의 합을 구하는 것인지에 대해 생각해볼 필요가 있다. 왜 1부터 n까지 모든 수의 약수를 구하라고 했는지를 알기 위해 아래 표를 살펴보자.

	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

위 표의 가로축은 1부터 8까지의 자연수, 세로축은 그 약수들을 나열해 놓은 것이다. 1은 1부터 8까지 모든 수의 공통 약수이다. 2는 2와 4, 8의 공통약수, 4는 4와 8의 공통약수인 것을 볼 수 있다. 여기서 우리가 힌트를 얻을 수 있다. 위에서 기술한 방식처럼 모든 수의 약수를 매번 구할 것이 아니라, 약수의 합만을 따로 구할 수 있다는 것이다. 

그럼 두번째 힌트, 약수와 배수와의 관계는 어떻게 생각해야 할까? 이 또한 위 표를 자세히 본다면 금방 떠올릴 수 있을 것이다. 1부터 n까지의 자연수 중 x의 배수의 갯수는 결국 n을 x로 나눈 몫과 같다. 

 

여기까지 왔다면 다음은 정말 간단한 코드 구현작업만이 남을 뿐이다. 1부터 N까지, 각 숫자 x에 n까지 존재하는 x의 배수(n을 x로 나눈 몫)곱하면 끝난다.

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

    n = int(n)

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

    print(sol)

 

O(n^2)의 시간복잡도를 가졌던 위의 오답풀이와는 달리, 이 풀이는 O(n)의 시간복잡도를 가진다.

 

 

참고)

사실 본인도 처음 풀었을땐 틀렸던 문제이다. 기초 난이도에서 나오는 문제이기에 단순 BruteForce 알고리즘 문제인줄 알았으나, 시간복잡도라는 개념과 백준 알고리즘에서는 O(n^2)일때 2000 이상의 입력값은 받을 수 없다는 것을 알고 다른 방법을 생각하게 되었다.

다만, 정답풀이 방법이 그리디(Greedy)알고리즘의 잔돈계산 문제와 유사한 측면이 있어 떠올릴 수 있는 풀이였다고 생각한다. 처음 알고리즘이나 코딩을 접하는 사람들은 답을 구하지 못했다고 실망하지 말고 비슷한 문제가 나왔을 때 이 풀이법을 생각해낼 수 있게 되었다는 것에 의의를 두면 될 것이다.