[C]백준 Q.17427 약수의 합 2

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

 

이전꺼의 제목이 약수였는데 왠지 모르게 2가 나왔다 

이 문제 다음순서는 1이다 왜?

 

아무튼 이번문제는 어떤 수의 약수들의 합을 구하고

1 ~ 어떤 수 까지의 약수들의 합을 다 더하는 문제다

 

문제에서 어떻게 하라고 적어있기에 그대로 역시 기초문제는 간단해서 좋다라며 코드로 적었건만...

시간초과로 틀렸다

// 시간초과나서 틀린 코드!


/// x의 모든 약수의 합값을 반환하는 함수
int f(int x) {
    int sum = 1 + x;
    int stop = x;
    for (int i = 2; i < stop; i ++) {
        if (x % i == 0) {
            sum += i;
            stop = x / i;
            sum += stop;
        }
    }
    return sum;
}

/// 주어진 x 이하의 모든 자연수값을 f(x)에 넣고 더한값을 반환하는 함수
int g(int x) {
    int sum = 1;
    for (int i = x; i > 1; i --) {
        sum += f(i);
    }
    return sum;
}

 

나름 깔끔히 잘했다고 생각했는데, 뭐 아무튼 검색좀 해보니 이런 문제는 에라토스테네스의 채 라는 별명의 가진 알고리즘으로 구현해야한다고 한다

무슨 이름이 이런가 했더니 내용보니 아 왠지 모르게 이런거 했었던 어렴풋한 기억이 난다

그런 기억이 있는거보면 꽤나 유명한모양?

 

뭐 아무튼 그래서 이 방법대로 전체를 더한 배열을 만들고

그 배열에서 더할걸 골라서 다 더한다

그리고 그냥 int도 아닌 long long~ 그렇게까지 큰범위를 다뤄야 하나 싶지만 예시가 Long으로 나와서 따라했다 

#define MAX 1000000

long long f[MAX + 1];

long long solution(int n) {
    // 각 i의 배수들의 합을 f배열에 저장
    for (int i = 1; i <= n; i ++) {
        for (int j = i; j <= n; j += i) {
            f[j] += i;
        }
    }
    
    // f[1] ~ f[n] 까지의 합
    long long g = 0;
    for (int i = 1; i <= n; i++) {
        g += f[i];
    }
    return g;
}

 

뭐 아무튼 그렇게 통과.

 

몇 문제 안풀어봤지만 백준문제들은 범위내에 미리 만들어두고 뽑아내는걸 좋아하는거 같기도하고?

 

 

 

https://github.com/wiwi-git/c-baekjoon

GitHub - wiwi-git/c-baekjoon: 블로그 업데이트용 백준 코드