수학: 백준 17427 약수의 합 2 파이썬(python)

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

17427번: 약수의 합 2

 

풀이:

입력받은 N보다 작거나 같은 자연수의 약수들의 합을 구해야 하는 문제입니다.

이 문제에는 0.5초의 시간제한이 있어 일반적인 약수 구하는 알고리즘은 시간 초과가 발생합니다.

 

문제를 풀기위해 제곱근을 사용하는 약수 알고리즘을 사용했었는데 시간 초과가 발생했고 어떻게 하면 풀 수 있을지 고민을 많이 했던 문제입니다. 

 

결국 구글링을 해서 구하는 방법을 알았고 문제를 풀 수 있었습니다.

입력 받은 N이 10일 경우

(10 // 10) * 10 => 10보다 작거나 같은 자연수들의 약수 중 10인 경우의 합

(10 // 9) * 9 => 10보다 작거나 같은 자연수들의 약수 중 9인 경우의 합

(10 // 8) * 8 => 8인 경우의 합

.

.

(10 // 1) * 1 => 1인 경우의 합

 

이 방법을 코드로 작성하면 답은 아래와 같습니다.

 

정답:

import sys
input = sys.stdin.readline

N = int(input())

def div(num):
    total = 0
    for i in range(1,num+1):
        total += (num // i) * i
        
    return total

print((div(N)))