[Python] 백준 17427번(약수의 합 2) 문제 풀이

 

def g(x):
    r = 0
    for i in range(1, x+1):
        r += f(i)
    return r

def f(A):
    divisors = []
    for i in range(1, A+1):
        if A % i == 0:
            divisors.append(i)
    return sum(divisors)
 
print(g(int(input())))

 

 처음에는 이렇게 f(A) 함수와 g(x) 함수를 둘 다 만들었다. 그런데 이렇게 하니 너무 당연하게도 시간 초과가 떴다.

 

def g(x):
    r = 0
    for i in range(1, x+1):
        r += i*(x//i)
    return r
 
print(g(int(input())))

 

 그래서 어떻게 할까 고민을 좀 하다가 구글링으로 어떤 블로그를 하나 찾았다.

 

https://from2020.tistory.com/27

백준 17427 - 약수의 합 2

 

 이 블로그이다. 이 블로그의 작성자가 찾은 규칙에 따르면, N = 10일 때 [1] [1, 2] [1, 3] [1, 2, 4] [1, 5] [1, 2, 3, 6] [1, 7] [1, 2, 4, 8] [1, 3, 9] [1, 2, 5, 10] 이다. 1이 10번, 2는 5번, 3은 3번... 10은 1번 들어가게 된다. 한마디로, N이 주어지면 1은 N번, 2는 N//2번, 3은 N//3번... N은 1번 들어가게 되는 것이다. 나는 그 합만 구해 주면 됐다. 진짜 저 블로그 작성자님께 존경을 표한다. 어떻게 이런 규칙을 찾아내시지.

 

 암튼 그렇게 짠 코드가 위 코드이다. 확실히 훨씬 간단해졌고 시간 초과도 뜨지 않았다.