약수의 합 2

문제

백준 17427번 - 약수의 합 2

언어

JavaScript

순서도

주어진 수 N 에 대해서 각각의 수에 대해서 배수의 개수 구하기
1 번 에서 구한 배수의 개수와 각각의 수를 곱해서 약수의 합 구하기
출력하기

문제 풀이 step 1

f(A) = A 의 모든 약수를 더한 값
- A = 12 라면,
- f(A) = 1 + 2 + 3 + 4 + 6 + 12 = 28
g(X) = X 이하의 모든 자연수 Y 의 f(Y) 를 더한 값
- X = 6 이라면,
- g(X) = f(1) + f(2) + f(3) + f(4) + f(5) + f(6)
주어지는 N 에 대해서 g(N)을 구해야 합니다.

문제 풀이 step 2

약수를 구하는 방법은 주어진 수 이하의 수들을 하나씩 나눠보면 됩니다.
- 예를 들어 주어진 수가 10 이라면, 10 에 대해서 1 ~ 10 까지의 모든 수로 나누어보고 나누어떨어지면 약수로 판별하면 됩니다.
- 이 방법의 시간 복잡도는 O(N) 입니다. 왜냐하면 1 ~ N 까지 총 N 번 연산을 하기 때문입니다.
그렇다면 이 방법을 이용해서 본 문제를 해결해보면 예상되는 시간복잡도는 O(N ^ 2) 입니다.
- 왜냐하면, N 이하의 모든 수에 대해서 각각 약수를 다 구해야 하기 때문입니다.
- 주어진 문제의 범위는 1,000,000 으로 시간복잡도는 1,000,000 의 제곱으로 1,000,000,000,000 입니다.
- 즉, 1 조로 너무 오래 걸립니다.
- 따라서 이 방법은 사용할 수 없습니다.

문제 풀이 step 3

약수 대신에 배수를 이용하면 쉽게 해결할 수 있습니다.
예를 들어 N = 12 라면,
- 12 이하의 수 중에서 1 의 배수는 12 개입니다.
  - 1, 2, 3, …, 12 모두 1 을 약수로 가지고 있습니다.
- 12 이하의 수 중에서 2 의 배수는 6 개입니다.
  - 2, 4, 6, 8, 10, 12 모두 2 를 약수로 가지고 있습니다.
- 12 이하의 수 중에서 3 의 배수는 4 개 입니다.
  - 3, 6, 9, 12 모두 3 을 약수로 가지고 있습니다.
- …
이렇게 각각의 수에 대해서 약수를 구하는 방법 대신에 N 에 대해서 각각의 수의 배수가 몇 개 있는지 파악하는 방법을 이용하면 시간복잡도는 O(N) 으로 주어진 시간 안에 해결할 수 있습니다.
문제에서 원하는 것은 각각의 약수를 더한 값이므로, 위의 방법을 통해서 구한 개수와 각각의 수를 곱해서 더한 값을 출력해주면 정답이 됩니다.
추가 설명은 주석으로 작성하겠습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const n = parseInt(input[0]);

	let sum = 0;
	for (let i = 1; i <= n; i++) {
		// 각각의 수의 배수의 개수 구하기
		const cnt = parseInt(n / i);

		// 구한 배수의 개수와 각각의 수를 곱해서 약수의 합 구하기
		sum += cnt * i;
	}

	return sum;
};

console.log(solution(input));