[BOJ] 17425 약수의 합 - JAVA

1. 문제

17425번: 약수의 합

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.

자연수 N이 주어졌을 때, g(N)을 구해보자.

---

2. 풀이

1.  long 타입 count배열에 f(x)값을 구하면서 탐색이 끝난 숫자는 누적합을 저장한다.

1-1.  i부터 i의 배수에 전부 i를 더한다.

1-2.  1-1이 끝났다면 count[i] += count[i-1]해서 누적합을 저장한다.

2.  T를 입력받은 후, T만큼 반복하면서 count[입력값]을 SB에 더해서 출력한다.

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

public class BOJ_17425_약수의합 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int END = 1000001;
      long[] count = new long[END];
      Arrays.fill(count,1);
      for(int i=2;i<END;i++){
         for(int j=i;j<END;j+=i){
            count[j] += i;
         }
         count[i] += count[i-1];
      }

      int T = Integer.parseInt(in.readLine());
      StringBuilder sb = new StringBuilder();
      for(int tc=0;tc<T;tc++){
         sb.append(count[Integer.parseInt(in.readLine())]).append('\n');
      }

      System.out.print(sb);
   }
}

---

3. 결과

count 배열의 타입을 잘못설정했다!