[BOJ17427][C++] 약수의 합 2

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

17427번: 약수의 합 2

문제

주어진 수 N 이하의 모든 자연수의 약수의 합들을 구하는 문제이다.

 

해결

시행착오(직관적 풀이)

1부터 N까지 돌며 모든 숫자의 약수의 합을 구하고, 그 합을 모두 더해 답으로 계산해냈다. 답은 맞게 나왔지만, 시간초과가 났다.

[코드]

#include <iostream>
#include <cmath>

using namespace std;

int N;
long long result = 0;

long long divisorSum(int num) {
	int sum = 0;

	for (int i = 1; i <= sqrt(num); i++) {
		if (num % i != 0) continue;
		sum += i;
		if (i == num / i) continue;
		sum += num / i;
	}

	return sum;
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

	for (int i = 1; i <= N; i++) {
		result += divisorSum(i);
	}

	cout << result;
}

1부터 N까지 돌기 -> O(N)

숫자 i를 1부터 루트(i)로 나눠 i의 약수의 합 구하기 -> O(루트(N))

=> 최종 시간복잡도 : O(N*루트(N))

1억 정도의 값의 처리시간이 1초인 것을 생각해보면, 1,000,000 * 1,000 = 10억 -> 약 10초가 소요될 것이다.

 

🎈Key Point🎈

f(1) = 1

f(2) = 1+2

f(3) = 1+3

f(4) = 1+2+4

f(5) = 1+5

f(6) = 1+2+3+6

f(7) = 1+7

f(8) = 1+2+4+8

f(9) = 1+3+9

f(10) = 1+2+5+10

.

.

 

여기서, N=10일 때를 생각해보면

1 -> 10개 (10/1)

2 -> 5개 (10/2)

3 -> 3개 (10/3)

4 -> 2개 (10/4)

5 -> 2개 (10/5)

...

10 -> 1개 (10/10)

의 규칙이 나타나는 것을 확인할 수 있다.

즉, N 이하의 자연수들의 약수에서 숫자 i(<=N)는 N/i 개가 나타난다.

 

위의 핵심 규칙을 사용하여 코드를 짜면 된다.

 

[전체 코드]

 

#include <iostream>

using namespace std;

int N;
long long result = 0;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

	for (int i = 1; i <= N; i++) {
		result += (N / i) * i;
	}

	cout << result;
}