[C++] 백준 17425 : 약수의 합

#include <iostream>

long long dp[1000001];
int main(int argc, char **argv){
    int T, N;
    long long sum = 0;
    scanf("%d",&T);

    for(int i = 1; i <= 1000001; i++){
        for(int j = i; j <= 1000001; j+=i){
            dp[j] += i;
        }
    }

    for(int i = 2; i <= 1000001; i++){
        dp[i] += dp[i-1];
    }

    for(int j=0; j<T; j++){
        scanf("%d", &N);
        printf("%lld\n",dp[N]);
    }

    return 0;
}

두번째로 푼 골드 문제. 역시 시간 초과에는 미리 값을 구해두고(에라토스테네스의 체), dp를 사용하는 것이 빠른 것 같다.

1	2	3	4	5	6	7
1	1	1	1	1	1	1 (1의 배수 dp값 더해줌)
	2		2		2	  (2의 배수 dp값 더해줌)
		3			3	  (3의 배수 dp값 더해줌)

이런식으로 쭉 에라토스테네스의 체를 이용하여 값을 더해주면 약수의 합 f(x)를 구할 수 있다.

하지만 우리가 원하는 것은 g(x)이므로 g(x) = f(x-1) + f(x)이므로 다이나믹 프로그래밍을 이용하여 이를 구해주면 된다.