[백준] C++ 알고리즘 17427번 - 약수의 합 2 문제

문제

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

17427번: 약수의 합 2

소스코드

#include <iostream>
#include <bits/stdc++.h>
using namespace std; 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    long long ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int temp = n / i;
        temp *= i;
        ans += temp;
    }
    cout << ans;
}

풀이

처음에는 2중포문을사용하여 약수를 다 구한값들을 더한값에다 ANS를 해주는 방법을 생각해보았는데, 시간초과로써 실패한 소스가 되었다.

결국엔 O(N)이 되도록 생각을 해야한다.

먼저 n의 배수는 n을 약수로 가진다.

즉 7까지들의 약수들을 생각해보면

7까지의 1의 약수의 개수 = 7개

7까지의 2의 약수의 개수 = 3개

 . . . 

즉 결론적으로 답을 도출해내는것은 흰부분에 있는 시트들을 전부 더한 값이 된다.