백준 17425 약수의 합, c++

 

 

 

첫번째 시도는 "시간 초과"였다.

#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;
    
    int arr[T];
    for(int i=0; i<T; i++)
        cin >> arr[i];
    
    for(int i=0; i<T; i++) {
        int sum_g = 0;
        for(int j=1; j<=arr[i]; j++) {
            int sum_f = 0;
            for(int k=1; k<=j/2; k++) {
                if(j%k==0)
                    sum_f += k;
            }
            sum_g += sum_f;
        }
        cout << sum_g << "\n";
    }
    
    return 0;
}

 

 

 

시간 복잡도 오류를 해결해야 했다.

3중 for문을 사용하지 않기 위해 여러 방식으로 코드를 고쳐봤지만 그래도 연산을 줄이지 못했다.

#include <iostream>
using namespace std;

int main() {
    
    //입력 받기
    int T;
    cin >> T;
    
    int arr[T];
    for(int i=0; i<T; i++)
        cin >> arr[i];
    
    // f(A)값, 1부터 1,000,000까지 각 약수의 총합 구해 저장
    int f[1000001];
    for(int i=1; i<=1000000; i++) {
        int sum_f = 0;
        for(int j=1; j<=i/2; i++) {
            if(i%j==0)
                sum_f += j;
        }
        f[i] = sum_f;
    }
    
    // g(A)값 구해 출력
    for(int i=0; i<T; i++) {
        int sum_g = 0;
        for(int j=1; j<=arr[i]; j++) {
            sum_g += f[j];
        }
        cout << sum_g << "\n";
    }
    
    return 0;
}

 

 

 

다른 사람들의 코드를 통해 시간 복잡도 문제를 해결해보았다.

약수 n은 n의 배수들이에게 나타남을 이용해 간단한 코드를 만드는 것이다. 

마지막에 '앞에 수까지의 모든 약수 합' 을 더해준다.

이렇게 배열에 각 g값을 저장해두고 마지막에 출력만 해주면 된다.

    // g값 계산하기
    for(int i=1; i<1000001; i++) {
        for(int j=i; j<1000001; j+=i){
            sum_g[j] += i;
        }
        sum_g[i] += sum_g[i-1];
    }