[수학][DP] BOJ 17425 약수의 합 - 오답노트

https://www.acmicpc.net/problem/17425

17425번: 약수의 합

 

- 문제 파악

약수의 합2 와 같은 문제라고 생각하고 풀이 시작, 하지만 Test Case 만큼 더 약수 계산을 수행해야한다.

 

- 나의 시도

1. 일단 무식하게 약수의 합2를 Test Case 수행

-> 시간초과

 

2. 배열에 미리 만들어 놓고 그것을 주어진 수에 대해서 빼야겠다고 생각

-> 하지만 배열에 어떤식으로 넣을지, 또 어떤식으로 출력할지 떠오르지 않음

 

- 정답

1. 에라토스테네스의 체 와 비슷한 알고리즘으로 먼저 1부터 N까지 각각의 약수의 합을 구해놓는다.

(에라토스테네스의 체  :  https://dhjkl123.tistory.com/33)

2. 1부터 N까지의 각각의 약수의 합을 더한 값의 점화식은 아래와 같다

n -> 1부터 N까지 각각의 약수의 합을 구해놓은 배열
arr -> 1부터 N까지 각각의 약수의 합을 전부 더하는 배열
arr[i] = arr[i-1] + n[i]

#include "bits/stdc++.h"

using namespace std;
  
vector<long long> d(1000001);
int main()
{
    int t; 
    cin>>t;
    vector<long long> f(1000001, 1);
    for (int i = 2; i <= 1000000; i++) 
    {
        for (int j = 1; i * j <= 1000000; j++) 
        {
            f[i * j] += i;
        }
    }
    for (int i = 1; i <= 1000000; i++) 
    {
        d[i] = d[i - 1] + f[i];
    }
    
    while (t--) 
    {
        int n; 
        cin>>n;
        cout<<d[n]<<"\n";

    }
    
    return 0;
}