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

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

17427번: 약수의 합 2

 

 

Sol)

#include <stdio.h>

int main()
{
    int N;
    long long sum = 0;

    scanf("%d", &N);

    for(int i = 1; i <= N; i++ ) {
        sum += (N / i) * i;
    }

    printf("%lld\n", sum);

    return 0;
}

 

• 풀이 방향

N이 최대 백만까지 될 수 있다. 시간제한이 0.5초이므로 O(N) or O(NlogN)으로 풀어야 한다. 1부터 N까지의 자연수들의 약수들을 모두 합해야 하기 때문에, 즉 f(1) + f(2) + ... + f(N-1) + f(N)은 필수적인 과정이므로, 시간 복잡도는 무조건 O(N)이상이 된다. 더하는 과정에 O(N)만큼의 시간을 사용해야 하니, 만약 2중 for문을 사용한다면 N이하의 각각의 자연수의 약수를 구하는 과정에서 O(1) or O(logN)이하의 시간을 써야 한다는 계산이 나온다. 하지만 약수를 상수시간 안에 구하는 방법은 없고 O(logN)안에 구하는 방법도 떠오르지 않았다. 따라서 2중 for문은 사용 할 수 없다는 결론이 나왔다. 그럼 for문을 한번만 쓰면서 구할 수 있는 방법이 뭐가 있을까? 규칙을 사용하면 된다. N이하의 자연수를 i라고 하면, i 들은 g(N)안에 (N /  i) * i 만큼 들어있다는 규칙을 발견할 수 있다. 

 

• 풀이

g(N)의 값이 integer범위를 넘어갈 수 있기때문에 long long으로 g(N)을 나타내는 변수인 sum을 선언해 준다. 그 후 1부터 N까지 위에서 발견한 규칙을 바탕으로 for문을 한번 돌려주면 끝난다.

 

• 문제에 대한 사견

코드도 짧고 간단한 문제였지만 풀이 과정을 생각해 내는게 어려운 문제였다. 도저히 주어진 시간제한 안에 풀 수 있는 알고리즘이 떠오르지 않는다면 규칙을 좀 더 적극적으로 찾아보는 것도 방법이 될 수 있을 것 같다. 답은 아니지만 아래에 2중 for문을 이용해 O(N*2) 과 O(N*√N)안에 약수를 구해 답을 내는 코드도 첨부한다.

 

- O(N*2)

#include <stdio.h>

int main()
{
    int N;
    long long sum = 0;

    scanf("%d", &N);

    for(int i = 1; i <= N; i++ ) {
        for(int k = 1; k <= i; k++)
            if(i % k == 0)
                sum += k;
    }

    printf("%lld\n", sum);

    return 0;
}

 

- O(N√N)

#include <stdio.h>

int main()
{
    int N;
    long long sum = 0;

    scanf("%d", &N);

    for(int i = 1; i <= N; i++ ) {
        for(int k = 1; k * k <= i; k++)
            if(i % k == 0) {
                if(k * k == i)
                    sum += k;
                else{
                    sum += k + i / k; //약수 k와 k에 대응되는 약수를 더해줌
                }
            }
    }

    printf("%lld\n", sum);

    return 0;
}