1. 문제 설명 📌

f(n) = n이란 숫자의 약수들의 합
g(n) = 1~n까지 각 숫자의 약수들의 합 즉 f(1) ~ f(n)의 합

2. 접근 방식 🗃️

KEY WORD: 누적 합, 시간 복잡도에 대한 감

f(n)을 구한다. (1~ 1000000 까지 전체 수에 대해 구한다.)
- 모든 f(n) 배열을 1로 초기화 (1은 무조건 약수에 포함되므로)
- f(ij) += i
  (i = 2 ~ 1000000까지 모두 순회, j = 1부터 1씩 증가함. 즉 `ij=i의 배수를 나타냄.`)
g(n)은 f(n)의 누적으로 구한다.
답을 출력한다.

f(i*j) = i를 진행하면, i의 배수에는 i를 무조건 더하고 i가 1~ 1000000까지 모든 수를 순회하기 때문에 각 숫자마다 자신의 약수를 빠짐없이 더할 수 있다. 여기서 다음이 궁금할 수 있다.

🤔 이렇게 무식하게 하면 시간 초과 안나나요?

나도 이 의문이 들었다. 하지만 다음과 같은 이유로 시간초과는 나지 않는다.

      for (int i = 2; i < MAX; i++) {
            for (int j = 1; i*j < MAX; j++) {
                fn[i*j] += i;
            }
        }

j는 MAX/i 번 반복한다. 따라서 50만, 33만, 25만 ... 점점 줄어든다. 조화 급수 형태이다.

위의 수식에서 1만 1000000으로 바뀐 것 뿐이다. 조화급수는 k가 커질수록 증가폭이 감소한다. 그리고 In(n)에 수렴한다. 따라서 위의 문제에서는 겉의 반복문은 N번 반복, 안의 반복문은 logN번 반복으로 상정해도 된다. 시간복잡도의 근사값을 구하면
O(N * logN)이다. 이는 10^7 ~ 10^8 사이이다.

시간초과는 나지 않는다.

3. 코드 소개 🔎

import java.io.*;
import java.util.Arrays;

public class Main {

    static int MAX = 1000001;

    public static void main(String[] args) throws IOException {

        int [] fn = new int [MAX];
        Arrays.fill(fn, 1);            // 초기값 1로 채우기
        long [] gn = new long [MAX];
        getFn(fn);
        getGn(fn,gn);

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder ans_list = new StringBuilder();
        for (int t = 0; t < T; t++) {
            ans_list.append(gn[Integer.parseInt(br.readLine())]).append("\n");
        }
        System.out.println(ans_list);
    }

    public static void getFn(int [] fn){
        for (int i = 2; i < MAX; i++) {
            for (int j = 1; i*j < MAX; j++) {    // i의 배수에는 i를 더한다. ➜ i *j라는 수의 약수를 더하는 것
                fn[i*j] += i;
            }
        }
    }
    public static void getGn(int [] fn, long [] gn){
        for (int i = 1; i < gn.length; i++) {
            gn[i] = gn[i-1] + fn[i];
        }
    }
}

4. 배운 것들 🎯

처음에는 에라토스테네스의 체를 활용했다.
소수인 값은 자기 자신과 1만 더하고, 아닌 값들은 (소수의 배수) + (N을 만들 때 파트너(곱해지는 수))로 구했다. 내가 간과한 지점은 어떤 소수의 배수 * 어떤 소수의 배수로 이루어진 약수는 계산에 넣지 않았다는 것이다. 해당 수는 소수들끼리의 조합, 배수와 소수 섞인 것, 배수끼리의 조합 등 가짓수가 많아서 특정할 수가 없었다.

어렵게 생각했다. :cry: 사실 i의 배수에 모두 i를 더한다.는 발상을 하지 못한 것이 문제였다. 나는 A라는 수의 영역에 들어올 값들을 일일히 구했다면, 정답 코드는 각 숫자가 자신이 있어야할 자리에 스스로 들어가도록 풀었다. 나는 모두 일일히 생각해야하게 구상해서 문제 풀이를 더 어렵게 만든 것 같다. 다음에 다시 풀어보겠다.