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

문제 링크 : 

www.acmicpc.net/problem/17427

17427번: 약수의 합 2

문제

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.

자연수 N이 주어졌을 때, g(N)을 구해보자.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 g(N)를 출력한다.

 

 

 

 

---

 

접근 방법 1

직관적으로 풀었더니 제한시간인 0.5초를 넘어서 시간초과가 떴다. f(1)부터 f(N)까지 하나씩 구해서 더하는 방식으로 짜면 안되는 것 같다.

#include <iostream>

using namespace std;


int main(){
    
    int N, ans=0;
    cin >> N;
    
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<=i; j++){
            if(i%j == 0) ans +=j;
        }
        
    }
    
    cout << ans << "\n";
    
    return 0;
}

 

 

 

 

 

 

접근방법 2

새로운 접근 방법으로 풀어보았다.

N = 10 일때를 보자.

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)

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

f(9) = sum(1, 3, 9)

f(10) = sum(1, 2, 5, 10)

 

이고 약수의 숫자들을 카운팅해보면, 

1 : 10개 (10을 1로 나눈 몫)

2 : 5개(10을 2로 나눈 몫)

3 : 3개(10을 3으로 나눈 몫)

4 : 2개(10을 4로 나눈 몫)

 

.

.

.

.

 

10: 1개(10을 1로 나눈 몫)

 

과 같이 규칙이 있음을 알 수 있다.

 

 

주의)

또한 처음에는 ans 변수를 int 형으로 선언했는데 오류가 났었다. 입출력 예시 자료를 보니 출력값이 82256014였고 이를 이진수로 변환하면 100111001110010000010001110(27비트)로 4바이트를 넘어가서 오류가 나는 거였다. 8바이트인 long long (int생략 가능) 으로 바꿔주니 정답처리가 되었다. 자료형에도 주의하자!!

 

 

#include <iostream>
using namespace std;

int main(){
    
    
    int N;
    long long ans=0;
    cin >> N;
    
    for(int i = 1; i<=N; i++){
        ans += (N/i)* i;
    }
    
    cout << ans << "\n";
    
    return 0;
}