[Algo Rhythm🕺💃] BOJ 17427 - 약수의 합 2

문제 분석

입력으로 주어지는 자연수를 $n (1 \le n \le 10^6)$ 그리고 $n$보다 작거나 같은 자연수를 $i$라고 하자.

자연수 $a$가 자연수 $b$로 나누어 떨어진다면 즉, $a$가 $b$의 배수라면 $b$는 $a$의 약수이다. 따라서, 이 문제는 $i$에 속하는 한 자연수의 배수의 개수와 그 자연수를 곱한 값들을 더하여 $g(n) = \sum_{i=1}^n f(i)$을 구하는 문제로 이해할 수 있다.

 

문제 풀이

$i$를 1부터 $n$까지 반복하여 $i$의 배수의 개수와 $i$를 곱한 값들을 더한다.

이때 $i$의 배수는 $n/i$개이다. 그리고 $i > n/2$일 때 $n$보다 작은 자연수들 중 $i$의 배수는 $i$ 자기 자신뿐이다. 따라서 그 경우에는 $i$만 더한다.

 

복잡도 분석

입력으로 주어진 자연수가 $n (1 \le n \le 10^6)$일 때, 시간 복잡도와 공간 복잡도는 다음과 같다.

⏰시간 복잡도 : $O(n)$

1부터 n까지 반복하면서 $g(n) = \sum_{i=1}^n f(i)$을 구하기 위해 $O(n)$이 소요된다.

🏠공간 복잡도 : $O(1)$

 

코드

 

문제 출처

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

17427번: 약수의 합 2