[백준 17425번] 약수의 합 (C++)

문제링크 : https://www.acmicpc.net/problem/17425

17425번: 약수의 합

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 1000000

ll dp[MAX];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
   
    int T, N;

    for(int i=1; i<=MAX; i++)  //약수의 합 (f(N))
    {
        for(int j=i; j<=MAX; j+=i)
        {
            dp[j] +=i;
        }
    }

    for(int i=2; i<=MAX; i++)  //약수의 합의 합 (g(N))
    {
        dp[i]+=dp[i-1];
    }

    cin >> T;
    while(T--)
    {
        cin >> N;
        cout << dp[N] <<"\n";
    }
    
    return 0;
}

시간초과 때문에 약수의 합을 미리 구하고 이를 통해 g(N)을 구하였다.

1이 포함될 때 -> 1이 약수일 때 각 배열에 1을 더해준다.

2가 포함될 때 -> 2가 약수일 때 각 배열에 2를 더해준다.

.

.

.

i가 포함될 때 -> i가 약수일 때 각 배열에 i를 더해준다.

이런식으로 약수의 합을 dp배열에 저장해준다.