백준 17425번 약수의 합 [C언어]

문제 출처: https://www.acmicpc.net/problem/17425

 

 

Sol)

#include <stdio.h>

#define MAX_INPUT 1000000

int main()
{
    int T, N;
    long long sum_of_div[MAX_INPUT + 1] = {0};

    for(int i = 1; i <= MAX_INPUT; i++){ //g(x)를 구하는 식
        for(int j = 1; i * j <= MAX_INPUT; j++){
            sum_of_div[i * j] += i;  //i를 약수로 가지는 수들에게 i를 더해줌
        }
        sum_of_div[i] += sum_of_div[i - 1]; //g(x)를 만들어주는 부분. 이 부분이 없다면 f(x)만 구하게 됨.
    }

    scanf("%d", &T);

    while(T--) {
        scanf("%d", &N);

        printf("%lld\n", sum_of_div[N]);
    }
    
    return 0;
}

 

• 풀이 방향

전에 풀었던 약수의 합 2 문제에 테스트 케이스만 추가 된 문제이다. 하지만 시간제한이 1초이고, 테스트 케이스의 최대값이 100,000에 N의 최대값이 1,000,000이기때문에 약수의 합 2 정답 코드에 테스트 케이스만큼 돌리는 for문을 씌우면 O(T * N) 만큼의 시간이 걸려 제한시간 1초를 넘어가게 되기때문에 답이 되지 않는다. 그렇다면 시간 제한을 맞추기 위해서는 어떻게 해야 할까? 일단 각 테스트 케이스에 맞춘 값들을 한번씩 print해야하기 때문에 최소 O(T)만큼의 시간은 든다. 따라서 2중 반복문을 이용해 시간복잡도를 O(T√N)으로 만들면 얼추 시간 안에 들어올 것 같았지만, O(√N)안에 g(N)의 값을 구하는 법을 찾을 수 없었다.

백준의 알고리즘 분류를 살펴보면 이 문제는 '에라토네스의 체' 라는 소수를 구하는 알고리즘 분류에 들어간다. 이 문제는 약수들의 합을 구하는 문젠데 왜 소수를 구하는 알고리즘이 쓰이지? 라고 생각할 수도 있지만, 잘 생각해보면 사실 에라토네스의 체는 소수를 체크하는 알고리즘이라기 보다는 '소수가 아닌 수'를 체크하는 알고리즘에 가깝다. 즉, 에라토네스의 체는 어떤 수 n을 약수로 가지는 수를 체크할 수 있는 알고리즘이라는 얘기다. 이 문제는 f(N), 즉 어떤 수의 모든 약수의 합을 구한 후 g(N) = f(N) + f(N - 1) + ... + f(2) + f(1) 을 구하는 문제이므로, 기존 에라토네스의 체 알고리즘을 응용해 i를 1부터 1,000,000까지 돌리면서 i를 약수로 가지고 있는 수를 나타내는 인덱스에 i를 더해주며 f(N)을 구하고, 이 f(N)들을 합해 g(N)을 구하는 식으로 진행해 주면 되겠다. 에라토네스의 체 알고리즘의 시간복잡도는 O(NloglogN)이므로 주어진 시간 제한을 만족시킬 수 있게 된다.

 

• 풀이

먼저, 에라토네스의 체 알고리즘을 사용할 때와 같이 배열을 입력값의 최대값 크기만큼 만들어 준다. 이 배열의 인덱스를 입력값과 1대1 대응 시키기 위해 크기를 1,000,001로 선언하고 0으로 초기화 해 줬다. 그 후, i * j, 즉 i를 약수로 가지고 있는 수에 대응되는 인덱스 공간에 i, 즉 i * j의 약수를 더해주는 과정을 1부터 1,000,000까지 반복해 준다. 여기까지만 하면 우리는 f(N)을 얻을 수 있지만, 우리가 원하는 것은 g(N)이므로, sum_of_div[i] 에 sum_of_div[i - 1]을 더해준다. 이는 f(N) + g(N - 1)과 같다. 이처럼 값을 계속 누적해 최종적으로는 sum_of_div라는 배열의 각 인덱스 공간에는 g(N)이 저장되게 해준다. 이해를 돕기 위해 이미지를 첨부한다.

검은색 숫자들은 에라토네스의 체 응용으로 각 인덱스가 가리키는 저장소에 저장되는 값들이다. 각 인덱스에 더해져 있는 검은색 숫자들의 합은 f(N)의 값을 나타낸다. 파란색 숫자는 실행되는 연산의 상대적인 순서를 나타낸 것이고, 빨간색으로 표시한 부분은 f(N) + g(N-1), 즉 위 코드의 sum_of_div[i] += sum_of_div[i - 1]을 표현한 것이다. 

 

• 문제에 대한 사견

에라토네스의 체를 응용해야 겠다는 생각도 쉽지 않았고, g(N)을 구해내는 부분또한 쉽지 않았던 문제였다. 유튜브를 보다가 "Prime numbers are not defiend by what they are. They are defined by what they aren't." 라는 말을 듣고 재미있어서 기억해 두고 있었는데, 이 문제를 풀 때 약간의 힌트가 된 것 같다.