약수의 합

문제

언어

  • JavaScript

순서도

  1. f 구하기
  2. g 구하기
  3. 출력 양식에 맞게 구하기

문제 풀이 step 1

  • 백준 17427번 - 약수의 합 2 풀이 와 유사하게 풀 수 있는 문제입니다.
  • 하지만 이번에는 테스트 케이스가 추가되었고, 추가된 테스트 케이스를 계산하는 만큼 소모하는 시간이 더 늘어났기 때문에 그만큼 더욱 빠른 방법으로 풀어야 하는 문제입니다.

문제 풀이 step 2

  • 문제의 개념을 다시 돌아보면,
  • 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)
  • 우리는 주어지는 테스트 케이스 t 마다 g(t) 를 구해주면 됩니다.
  • 각 자연수 k 에 대해서 g(k) 값을 알고 있으면, 어떤 테스트 케이스가 들어와도 문제에서 원하는 값을 출력할 수 있습니다.
  • 그래서 우선 g 값을 모두 구할 것입니다. 그리고 g 값을 구하기 위해서 먼저 f 값을 모두 구합니다.

문제 풀이 step 3

  • f 값을 구하는 방법은 자연수 k 에 대해서 k 이하의 수들을 하나씩 나눠보면 됩니다.
    • 하지만 이 방법은 시간이 너무 오래 걸립니다.
  • 이번에도 약수 대신에 배수를 이용하면 더욱 빠르게 해결할 수 있습니다.
    • f[i] = i 이하의 모든 약수를 더한 값 입니다.
      • 1 의 경우, 1 은 모든 자연수의 약수이므로, 모든 f[i] 는 1 을 가지고 있습니다.
      • 2 의 경우, 2, 4, 6, 8, … 과 같이 2 의 배수들은 2 를 약수로 가지고 있습니다. 따라서 모든 f[2 x k] 는 2 를 가지고 있습니다.
      • 3 의 경우, 3, 6, 9, 12, … 과 같이 3 의 배수들은 3 을 약수로 가지고 있습니다. 따라서 모든 f[3 x k] 는 3 을 가지고 있습니다.
      • …
      • 1,000,000 의 경우, 최대값이 1,000,000 이므로 1,000,000 의 배수는 1,000,000 밖에 없습니다. 따라서 f[1000000] 은 1,000,000 을 가지고 있습니다.
    • 위의 방법처럼 “어떤 수의 배수는 어떤 수를 약수로 가진다” 라는 아이디어를 이용해서 밑에서부터 한 단계씩 올라가면서 f 값을 채워줍니다.

문제 풀이 step 4

  • 위 과정을 통해서 구한 f 값을 이용해서 g 값을 구해주면 됩니다.
  • g[i] = f[1] + f[2] + … + f[i] 입니다.
    • g[1] = f[1]
    • g[2] = f[1] + f[2]
    • g[3] = f[1] + f[2] + f[3]
    • …
    • g[1000000] = f[1] + f[2] + f[3] + … + f[1000000]
  • g 값을 “g[k] = g[k - 1] + f[k]” 라는 식을 얻을 수 있습니다. 이 식을 이용해서 각 g 값을 구해줍니다.
  • 그리고 주어진 테스트 케이스마다 g 값을 출력해주면 정답이 됩니다.
  • 추가 설명은 주석에 작성하겠습니다.

후기

  • 제가 정말 가고 싶었던 기업의 면접에서 나온 문제와 유사했던 문제입니다.
  • f 를 구하는 방식이 “약수 대신 배수를 이용한다” 라는 뭔가 있어보이는 말을 사용했습니다.
  • 물론 “약수 대신 배수를 이용한다” 는 것이 중요한 포인트이긴 합니다.
  • 하지만, 결론적으로 에라토스테네스의 체를 구하는 방식과 별반 다르지 않습니다. 거의 똑같다고도 말을 할 수 있겠습니다.
  • 너무 아쉬워서 잊혀지지 않을 것 같습니다. 그래도 제대로 이해하는 계기가 되었습니다.

소스 코드

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

const solution = (input) => {
	const MAX = 1000000;
	let t = parseInt(input[0]);
	const arr = input.slice(1).map(Number);

	// f(A) = 자연수 A의 모든 약수를 더한 값
	const f = Array.from({length: MAX + 1}, () => 1);

	// g(x) = 자연수 x 이하의 모든 자연수 y 의 f(y) 값을 더한 값
	const g = Array.from({length: MAX + 1}, () => 0);

	// 1. f 구하기
	for (let i = 2; i <= MAX; i++) {
		for (let j = 1; i * j <= MAX; j++) {
			// "i 의 배수는 i 를 약수로 가진다" 따라서 i 의 배수에 대해서 i 를 다 더해준다.
			f[i * j] += i;
		}
	}

	// 2. g 구하기
	for (let i = 1; i <= MAX; i++) {
		// g 값은 이전의 한 단계 전의 g 값을 이용해서 쉽게 구할 수 있습니다.
		g[i] = g[i - 1] + f[i];
	}

	// 3. 출력 양식에 맞게 구하기
	let res = "";
	let index = 0;
	while (t-- > 0) {
		res += `${g[arr[index++]]}\n`;
	}

	return res;
};

console.log(solution(input));