[백준/c++] 17425번: 약수의 합

 

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

17425번: 약수의 합

 

 

 

https://nyeoungkm.tistory.com/entry/백준c-17427번-약수의-합-2

[백준/c++] 17427번: 약수의 합 2

 

 

이 문제와 동일한데, 시간 초과가 걸린다ㅎㅎ 그래서 분명 memoization을 통해서 시간 초과를 줄일 수 있을 거 같다는 생각이 들었다.

이럴 땐, 예제를 하나 잡고 해 보면 됨

 

N = 4라면

1  -> [1]

2 -> [1] , [1,2]

3 -> [1], [1, 2], [1, 3]

4 -> [1], [1, 2], [1, 3], [1, 2, 4]

 

이렇게 진행된다. 딱 봐도 dp를 사용해서 하면 충분할 듯싶다 

dp를 진행하려면 이전 값(N이하 자연수의 약수 합)들에 내 값(N의 약수 합)을 더하면 되는데,, N의 약수의 합을 어떻게 하면 되는지..

이중 for문을 사용해서 

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

 

이것도 직접 해보면

i=1 
j=1 dp[1] = 1
j=2 dp[2] = 1
j=3 dp[3] = 1
j=4 dp[4] = 1

i=2
j=2 dp[2] = 1 + 2
j=4 dp[4] = 1 + 2

i=3
j=3 dp[3] = 1 + 3

i=4
j=4 dp[4] = 3 + 4

 

for문으로 dp를 memoization 해서 dp [n]을 출력할 수 있다.

 

---

 

#include <iostream>
#include <algorithm>
#define MAX 1000000
using namespace std;
long long dp[1000001];

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;
    cin >> t;
    
    for(int i=1; i<=MAX; i++) for(int j=i; j<= MAX; j+=i) dp[j] += i;
    for(int i=2; i<=MAX; i++) dp[i] += dp[i-1];
    
    while(t--){
        int n;
        cin >> n;
        cout << dp[n] << '\n';
    }
    return 0;
}