[Python] 17427 - 약수의 합2 (실버2)

1. 문제 설명

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

17427번: 약수의 합 2

 

---

2. 아이디어

N의 범위가 1,000,000이므로 이걸 무식하게 약수를 매번 구하는 이중 for문으로 해결하려 하면

시간 복잡도가 O(n√n)이므로 0.5초 내로 해결하는 것은 무리다.

 

이럴 때 필요한 것이 바로 "music is my life". 무식이 내 삶이란 소리다.

직접 한번 패턴을 분석해보자.

1부터 10까지 약수를 잘 살펴보면

1은 계속해서 나오고, 2는 2의 간격으로, 3은 3의 간격으로 등장한다.

이게 어떤 의미냐면 1, 2, 3, 4, 5, ...를 관점으로 for문을 돌리지 않고

1의 개수, 2의 개수, 3의 개수, ...를 관점으로 for문을 돌리는 것이 가능해지는 것이다.

사실 이걸 찾아내는 게 어렵지 여기까지 왔다면 충분히 해결가능한 문제였다.

 

---

3. 코드

def solution():
    n = int(input())
    result = 0
    
    for current in range(1, n + 1):
        result += current * (n//current)
    print(result)

solution()