[Java] 백준 17425번 - 약수의 합

 

먼저 dp배열을 만든 후, 모든 수는 1을 약수로 가지기 때문에 1(1개)로 채워준다.

그 후 dp를 1개씩 확장해나가면 되는데, 누적합을 구하는 것이므로 dp[i]에 dp[i - 1]을 먼저 더해준다.

for문에서는 자기 자신을 약수로 가지는 수에 대해 수를 더한다.

예를 들어 현재 i가 2면, dp[2]에 dp[1]을 넣어 1의 약수 개수를 먼저 더한 후, 

2를 약수로 가지는 4, 6, 8, 10 ...에 2를 더해주는 것이다. 이 동작을 dp의 마지막까지 해준다.

에라토스테네스의 체를 변형한 느낌이라고 볼 수 있다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
long[] dp = new long[1_000_000+1];
Arrays.fill(dp, 1);
for (int i = 2; i < dp.length; i++) {
    dp[i] += dp[i - 1];
    for (int j = 1; i * j < dp.length; j++) {
        dp[i * j] += i;
    }
}

int testcase = Integer.parseInt(br.readLine());
for (int t = 0; t < testcase; t++) {
    int N = Integer.parseInt(br.readLine());
    bw.write(dp[N] + "\n");
}
bw.flush();
bw.close();
br.close();