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

 

 

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

17427번: 약수의 합 2

 

try 01

N보다 작거나 같은 자연수의 약수를 모두 구하고 그 값을 더 했다. 역시나 시간 초과 (제한시간 0.5초 일 때부터 알아봤다..ㅜ)

 

[시간 초과 나오는 코드]

int countNumber(int x){
    int cnt = 1; //1
    for(int i=2; i<=x; i++){
        if(x % i == 0) cnt+=i;
    }
    return cnt;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    int sum = 1;
    //N보다 작거나 같은 자연수의 약수 구하기
    for(int i=2; i<=n; i++){
        sum += countNumber(i);
    }
    cout << sum << '\n';
    return 0;
}

 

 

---

try 02

규칙이 있을 거 같으니... 규칙을 한번 찾아보자

이런 문제는 한 예제를 잡고 규칙을 찾는 게 좋은 거 같다.

 

N=4

f(1) = 1

f(2) = 1 + 2

f(3) = 1 + 3

f(4) = 1 + 2 + 4

↓

각 자연수 약수에 등장하는 수의 개수

1 = 4

2 = 2

3 = 1

4 = 1

 

→ i는 (N / i) 개 나옴. 그러므로 (N / i) * i 

 

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    long long gn = 0;
    for(int i=1; i<=n; i++){
        gn += (n/i)*i;
    }
    cout << gn << '\n';
    return 0;
}