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

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

728x90

처음에는,, N보다 작은 자연수의 약수를 하나씩 구해서 다 더한값을 리턴하는걸로

동적계획법을 사용해서 코딩을 했는데 당연히 시간초과가 났다.

 

어쨌든 수학 카테고리에 있는거니까, 아마 동적계획법과는 상관 없을거라고 생각하고,

하나씩 풀어서 해봤다.

한 10까지 해 보니까 약수의 합이라고 하는게

결국은 n을 1부터 나누었을때의 몫을 다 더하면 되는거였다.

 

예를들어서 n이 6이라고 했을때,

1은 6번(1*6)

2는 3번(2*3)

3은 2번(3*2)

4는 1번(4*1)

5는 1번(5*1)

6은 1번(6*1)

다 더하면 33이 나온다.

 

실제로 약수를 구하면

1:1

2: 1,2

3: 1,3

4: 1,2,4

5: 1,5

6: 1,2,3,6

 

이렇게 되는데 나오는 횟수가 결국은 n을 나누어 나온 몫이라는것을 알 수 있다.

 

N=int(input())
ans=0
for i in range(1,N+1):
    ans+=i*(N//i)

print(ans)