약수의 합 2 - 백준 17427 [Python]

Example)

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

 

문제해석)

f(A)

- O(루트A) (1~A를 모두 나누어보는 방법)

- O(A) (1~A를 모두 나누어보는 방법)

 

g(N)

- N*O(루트N) = O(N루트N)

- N*O(N) = O(N^2)

 

이때, 시간 제한이 0.5초기 때문에 약수를 구한다음 더하는 방법은 불가능하게 된다.

따라서 약수의 반대는 배수이다. 라는 아이디어로 문제를 해결해 본다.

( 3의 배수는 3을 약수로 갖는 수 / 5의 배수는 5를 약수로 갖는 수 라는 컨셉을 이용 )

• N이하의 자연수 중에서 1을 약수로 갖는 수의 개수는 [N/1]개
• N이하의 자연수 중에서 2를 약수로 갖는 수의 개수는 [N/2]개
• N이하의 자연수 중에서 3를 약수로 갖는 수의 개수는 [N/3]개
• ...
• N이하의 자연수 중에서 i를 약수로 갖는 수의 개수는 [N/i]개

그러므로, 이를 구하기 위해서는 반대로

1*[N/1] + 2*[N/2} + 3*[N/3] ... + N*[N/N] 를 계산하여 정답을 구하면 된다. 따라서 O(N)시간을 통해 구할 수 있다.

 

정답)

n = int(input())

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