[백준 17427 C++][S2] 약수의 합 2

⭐️ 난이도

Silver 2

---

⭐️ 문제

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

17427번: 약수의 합 2

 

---

⭐️ Idea flow

 

문제를 간단하게 정리해보자.

자연수 x가 주어졌을 때, x의 약수들을 모두 더한 값을 f(x)라고 하자.
자연수 n이 주어졌을 때, n보다 작거나 같은 모든 자연수들의 f(n)의 합을 g(n)이라고 하자.
g(n)을 구하라.

 

[시간 초과난 알고리즘]

처음에는 1부터 n까지 for문으로 돌면서, 각 수에 대해 약수를 구하는 코드를 돌리면서 모든 합을 더하는 방법을 사용했다.

하지만 이렇게 하니 시간초과가 났다.

n의 최댓값이 1,000,000인데 함수가 중첩되어 있어 실제 구조는 이중 for문이다.

for문이 최대로 도는 횟수는 500,000 * 1,000,000 = 500,000,000,000이기 때문에 0.5초를 훨씬 넘는다는 것을 알 수 있다.

void getDivisor(int x){
    long long cnt = 0;
    for(int i = 1; i / 2 <= x; ++i){
        if(x % i == 0){
            cnt += i;
        }
    }
    result += cnt;
}

void solve(){
    long long result = 1;
    for(int i = 2; i <= n; ++i){
        getDivisor(i);
    }
    cout << result;
}

 

 

[통과한 알고리즘]

위의 풀이를 통해서 시간 복잡도를 O(n^2) 밑으로 내려야 한다는 것을 알 수 있다.

이왕이면 O(n)으로 하는 것이 좋을 것이다.

 

n = 7일 때를 예로 들어보자. 각 수에 대해서 f(x)를 구해보자.

f(1) = sum(1)

f(2) = sum(1, 2)

f(3) = sum(1, 3)

f(4) = sum(1, 2, 4)

f(5) = sum(1, 5)

f(6) = sum(1, 2, 3, 6)

f(7) = sum(1, 7)

이제 각 숫자가 몇 번 나왔는지 카운트해보자.

 

1은 7번
2는 3번
3은 2번
4는 1번
5는 1번
6은 1번
7은 1번이다.

잘 살펴보면 각 숫자가 나오는 횟수는 n에서 각 숫자를 나눈 몫만큼 등장하는 것을 알 수 있다.

이 방법을 사용하면 for문 한 번으로 가능할 것이다.

 

 

---

⭐️ Code

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>

#define INF 10000000000000
using namespace std;

// 17427 - 약수의 합 2
int n;
long long result = 0;


void input(){
    cin >> n;
}

void solve(){
    //각 숫자가 나오는 횟수는 n에서 각 숫자를 나눈 후의 몫만큼 등장한다.
    for(int i = 1; i <= n; ++i){
        result += (n / i) * i;
    }
    cout << result;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    solve();

    return 0;
}