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

문제 분석

약수의 성질 중 하나는 두 자연수 $a, b$에 대하여 $a$가 $b$의 배수이면 $b$는 $a$의 약수(들) 중 하나라는 것이다.

그리고 이 문제는 자연수 $n(1 \le n \le 10^6)$을 입력할 때 $g(n)$을 출력할 것을 요구한다. 이때 $g(n)$은 아래와 같은 수식으로 정의할 수 있다.

$g(n)= \begin{cases} g(n - 1) + f(n) & n \gt 1\\ 1 & n = 1 \end{cases}$

 

앞서 말한 두 가지를 종합할 때 이 문제는 약수의 성질을 이용하여 모든 $n$에 대하여 $g(n)$을 구하여 저장한 다음 테스트케이스로 $n$에 속하는 자연수 $a$가 들어올 때마다 $g(a)$를 출력하는 문제로 이해할 수 있다.

 

문제 풀이

1. $g(n)$을 저장하는 배열 $acc$를 생성한다. 그리고 1부터 $10^6$까지 자연수 $x$에 대하여 차례대로 2번 과정을 반복한다.

2. $x$부터 $10^6$까지 $x$씩 증가하며 $x$의 배수 $y$(들)을 찾는다. 그리고 $acc[y]$에 $x$를 더한다. 왜냐하면 약수의 성질에 의

    해 $x$는 $y$의 약수(들) 중 하나이기 때문이다. 2번 과정은 $g(n)$에 $f(n)$을 더하기 위한 과정이다.

3. 2번 과정이 끝나면 $acc[x]$에 $acc[x-1]$을 더한다. 3번 과정은 $g(n)$에 $g(n-1)$을 더하기 위한 과정이다.

 

복잡도 분석

입력으로 주어지는 자연수를 $n (1 \le n \le 10^6)$, 테스트케이스의 개수를 $t(1 \le t \le 10^5)$라고 할 때, 시간 복잡도와 공간 복잡도는 다음과 같다.

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

$n$ 에 속하는 자연수 $i$와 그 배수인 $j$(들)에 대하여 $acc[i]$를 구하기 위해 $n \div i$번 $acc[j]$에 $i$를 더하는 과정을 반복하기 때문에 $O(n^2)$만큼 소요된다. (근데 확신하진 못 하겠다...😥)

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

$g(n)$을 저장하는 배열 $acc$를 생성하기 위해 $O(n)$만큼의 공간이 필요하다.

 

 

코드

	#include <cstdio>
	#define MAX 1000001
	typedef long long ll;
	ll acc[MAX + 1];
	int main()
	{
	int t, n;
	for(int i = 1; i <= MAX; i++)
	{
	for(int j = i; j <= MAX; j += i)
	acc[j] += i;
	acc[i] += acc[i - 1];
	}
	scanf("%d", &t);
	for(int i = 0; i < t; i++)
	{
	scanf("%d", &n);
	printf("%lld\n", acc[n]);
	}
	return 0;
	}

view raw boj17425.cpp hosted with ❤ by GitHub

 

문제 출처

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

17425번: 약수의 합