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

---

소스코드

N = int(input())

ans = 0

for i in range (1,N+1):

  ans += (N//i) * i

print(ans)

---

알고리즘

틀린풀이

N = int(input())

def sum_yaksu(n):    

    return sum([i for i in range(1, n+1) if n % i == 0])

ans = 0

for i in range (1,N+1):

  ans += sum_yaksu(i)

print(ans)

문제 그대로 약수의 합을 구하는 함수를 만들고 for문을 돌면서 합을 구하는 알고리즘을 짰는데 시간 초과가 났다.

DP문제도 아니고 이거에서 시간을 어떻게 줄일까 생각하다가 수학적으로 접근해야하는 문제임을 깨달았다.

---

진짜 설명

6까지 더해야 한다고 할때

1 -> 1 ( 1 )

2 -> 3 ( 1 + 2 )

3 -> 4 ( 1 + 3 )

4 -> 7 ( 1 + 2 + 4)

5 -> 6 ( 1 + 5 )

6 -> 12 ( 1 + 2 + 3 + 6)

( N // i ) * i 이 부분인데 어떤 수의 배수는 그 숫자를 약수로 갖는다.

그렇다면 N 이하의 숫자 중에서 i를 약수로 갖는 경우는 N/i 개 이다.

위의 예시에서 볼 수 있듯

1을 약수로 갖는 경우는 (6/1) 6개

2를 약수로 갖는 경우는 (6/2) 3개

등등 이다.

따라서 약수의 합은 개수 X i를 해주면 된다.