백준 boj 17427 - 약수의 합 2 (파이썬, python)

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

17427번: 약수의 합 2

 

 

문제의 난도는 높지 않으나, 시간 초과를 고려해야 하는 부분이 까다롭다.

첫 시도에 2중 반복문을 활용하였으나, 당연히 실패...

하여 얻은 인사이트는

 

만약 10을 기준으로 한다면,

1 은 총 10번 등장하고 ((10 / 1) * 1),

2 는 총 5번 등장하고 ((10 / 2) * 2),

3 은 총 3번 등장하고 ((10 / 3) * 3),

4, 5 는 총 2번 등장하고 ((n (10) / i ( 4 ~ 5 )) * i ( 4 ~ 5 )),

6, 7, 8, 9, 10 은 총 1번 등장한다 ((n (10) / i ( 6 ~ 10 )) * i ( 6 ~ 10 )).

 

수식으로 정리하면

( n / i ) * i

이 된다.

 

코드

n = int(input())

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