백준 17425번 : 약수의 합

백준 17425번 : 약수의 합

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        long[] numArray = new long[1000001];
        Arrays.fill(numArray,1);
        for(int i = 2; i<numArray.length; i++){
            for(int j = 0; j*i<numArray.length; j++){
                numArray[i*j] += i;
            }
            numArray[i] = numArray[i-1] + numArray[i];
        }
        int count = Integer.parseInt(br.readLine());
        while(count-->0){
            int inputNum = Integer.parseInt(br.readLine());
            sb.append(numArray[inputNum]).append("\n");
        }
        System.out.print(sb);
    }
    public static void main(String args[]) throws IOException {
        new Main().solution();
    }
}

처음엔 백준 17427번 : 약수의 합2 (https://www.acmicpc.net/problem/17427) 을 먼저 풀었기 때문에 동일한 로직에 그저 입력값만 여러개 받을 수 있게 while문으로 받았는데, 시간초과가 나왔다. 어떻게 풀어야 하는지 고민하다가 힌트를 얻고자 알고리즘 분류를 확인 했다. 거기서 에라토스테네스의 체 알고리즘(https://www.acmicpc.net/problem/2960)을 읽어보았다. 내용은 배열을 초기화하고, 2 이상의 제일 낮은 숫자의 배수부터 배열에서 제거해 나가면 결국은 1과 자기 자신으로만 나눌 수 있는 소수만 남게되는 알고리즘 이였다. 그러면 이 문제는 결국 특정 숫자까지 배열을 초기화하고 그 안에 값을 특정 인덱스까지의 g(N)의 값들로 초기화 하는 건가? 하고 생각을 했다. 하지만 아무리 생각해도 특정 숫자 (입력 값 : 1, 2, 10, 70, 10000) 까지의 for문보다 배열을 초기화하는 과정에서의 for문의 횟수? 가 더 많아서 시간초과 문제를 해결할 수 있는지 의문이었다. (시간 복잡도의 대한 공부가 부족했습니다) 결국 검색을 통해 정답을 확인 했고, 내가 처음에 생각한 것과 매우 흡사한, 거의 동일한 내용이었다. 검색을 통해 생각에 대한 확신을 얻었고, 문제를 해결했다. 여기서 두 가지의 느낀 점이 있다. 첫 번째 시간복잡도를 제대로 공부하자. 공부가 부족해 힌트를 통해 정답의 유추에 성공하였음에도 확신을 가지지 못했다. 두 번째 일단 시도해보자. 확신이 없었기 때문에 도전하지 못했지만, 매번 확신이 있어야지만 도전하는 것도 나 스스로를 나태하게 만드는 점 중에 하나일 수도 있겠다라는 생각을 했다. 

 

풀이 결론

모든 인덱스에 숫자 1을 초기화 (모든 수의 약수이기 때문에)

각 인덱스마다 브루트포스로 배수의 값을 추가

 

ex)

Array[2] += 2 ... Array[14] += 2 ...

Array[3] += 3 ... Array[12] += 3

 

그러면 숫차적으로 각 인덱스마다 그 해당하는 자연수의  약수들의 값이 더 해진다.

그러면 각 인덱스엔 인덱스에 맞는 약수들의 합이 담겨져 있다. 하지만 우리가 구하고자 하는건

특정 자연수 N까지의 g(n)이기 때문에 

g(i) = f(i-1) + f(i)를 순차적으로 반복해서 더 해주고 그 값으로 초기화를 해준다.

 

ex)

index[2] = 1 + 3 ... index[3] = 4 + 4 ... index[4] = 8 + 7

 

그리고 입력 받은 count대로 값을 입력 받아 값의 인덱스를 출력해주면 된다.