[백준] 17425번 - 약수의 합 (Gold 5)

문제 링크

백준 17425번 - 약수의 합 (Gold 5)

문제 설명

참고 문제 : 백준 17427번 - 약수의 합 2 (Silver 2)
N을 T개 입력받고, 각각의 N에 대해 g(N)을 출력하는 문제이다.

주의점

• overflow에 주의해야한다.
  • $g(N) = O(N^2)$, $g(1000000) \approx 2^{40}$ : int의 범위를 넘는다.
• 시간복잡도에 유의해야한다.
  • $O(N \sqrt N)$으로는 시간 초과가 뜬다.

정답 코드 및 설명

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        long g[] = g(1000000);
        for(int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            bw.write(""+g[N-1]);
            bw.newLine();
        }
        bw.close();
    }
    
    static long[] g(int N) {
        long g[] = new long[N];
        long f[] = new long[N];
        g[0] = 1;
        for(int i = 1; i <= N; i++) {
            for(int j = i; j <= N; j += i) {
                f[j-1] += i;
            }
            if(i > 1) g[i-1] = g[i-2] + f[i-1];
        }
        return g;
    }
}
    

• 백준 17427번 - 약수의 합 2 (Silver 2)처럼 풀 경우 시간 복잡도 : $O(N^2)$

• $g(1), … , g(1000000)$을 전부 계산하므로 보다 효율적인 계산이 가능하다.

  • $g(i) = g(i-1) + f(i)$, $f(i) = \displaystyle \sum_{j|i} j$
  • 역으로 생각하기 : $f(i)$를 계산할 때 $j$는 모든 $j$의 배수들에 더해진다.
  • 배열 $f[1000000]$을 만들고 $j$의 배수마다 $j$를 더해주면 된다!
  • 배열 $f[1000000]$ 계산의 시간 복잡도
    • $O(N/1) + O(N/2) + \cdots + O(N/N) = O(N\log N)$
  • 전체 시간 복잡도 : $O(N) + O(N\log N) = O(N\log N)$

• g(N)이 int의 범위를 벗어날 수 있으므로, long으로 구현한다.