[백준 17427]약수의 합2 - 파이썬 풀이

문제 출처

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

17427번: 약수의 합 2

• 1부터 자연수 N까지의 수들의 약수를 모두 더하는 문제이다.
•  

나의 풀이

처음엔 1부터 N까지 약수를 하나씩 구해가면서 더했다. 당연히 시간 초과가 났다. N(1 ≤ N ≤ 1,000,000)이라서 모든 약수를 하나씩 구하면 절대 시간 안에 풀 수 없다.
자연수 N을 K로 나눴을 때 나머지가 0이면 K는 N의 약수이다. 약수는 사실 N = X * K 꼴로 표현할 수 있는데 이 표현은 N이 K의 배수라는 말과 같다.

그리고 N이하에서 K의 배수 개수는 N//K로 쉽게 구할 수 있다.

 

예시) N이 10

(10//1) * 1 =  10 * 1 = (10 이하에서 1을 약수로 갖는 숫자 개수) * 약수 1

(10//2) * 2 =  5 * 2 = (10 이하에서 2를 약수로 갖는 숫자 개수) * 약수 2

(10//3) * 3 =  3 * 3 = (10 이하에서 3을 약수로 갖는 숫자 개수) * 약수 3

...

...

(10//9) * 9 = 1 * 9 =  (10 이하에서 9를 약수로 갖는 숫자 개수) * 약수 9

(10//10) * 10 = 1 * 10 = (10 이하에서 10을 약수로 갖는 숫자 개수) * 약수 10

그리고 각 숫자를 다 더하면 모든 약수의 합으로 총 87이 나온다~

작성한 코드

• 사용 언어 : 파이썬

def main():
    n = int(input())
    result = 0
    result += sum_divisor(n)
    print(result)


def sum_divisor(n):
    if n == 1:
        return 1
    divsum = 0
    for i in range(1,n+1):
        divsum += (n//i)*i
    return divsum


if __name__ == '__main__':
    main()

느낀 점

약수로 무언가 해야 할 때 규칙이 필요하다면 배수를 이용해보자!!! 

처음 풀이로 시간 초과를 내고 계속 생각해보다가 잘 모르겠어서 다른 사람들의 풀이를 참고했다.

약수의 성질을 생각하면 쉬운 문제였는데 그 성질을 생각하는 게 쉽지 않았다.

이게 백준 코딩 테스트 수학 기초에 있는 문제인데 이렇게 막히는 걸 보면 알고리즘 기초공사가 많이 부실한 것 같다.

이런 기초 문제에 대한 지식이 쌓여야 더 어려운 문제에도 접근할 수 있는 것 같다. 앞으로 기초 문제라고 얕보지 말자..!