[C언어]백준(BOJ) 17427 - '약수의 합2'

#문제 분석

문제 링크 | https://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)로 표현한다.

 

KEY 1 | f(A) 는 자연수 A에 대한 모든 약수의 합이다. 

-> ex. A가 4라면 f(4) 는 1+2+4 = 7

KEY 2 | y는 x보다 작거나 같은 모든 자연수들이다.

-> ex. x가 4라면 y는 1,2,3,4

KEY 3 | g(x)는 f(y)값의 합들이다.

-> ex. x가 4라면 y는 1,2,3,4이고, 1은 약수 1 / 2는 약수 1, 2 / 3은 약수 1, 3 / 4는 약수 1, 2, 4 를 가진다. 이 약수들의 합은 1 + 1 + 2 + 1 + 3 + 1 + 2 + 4 = 15 가 된다. 

 

---

#기본 개념

크게 이 문제를 풀기 위해 알아둬야 할 기본 개념을 2가지 라고 생각했습니다. 

 

첫 번째는 i가 N의 약수일 때 (N / i) * i는 N이 된다는 것.

두 번째는 i가 N의 약수가 아닐 때 (N/i)는 N보다 작거나 같은 i의 배수 중에서 최대값이 된다는 것. 

 

두 가지 기본 개념에 대해 예시를 들어보겠습니다.

 

 

첫 번째 두 번째 다 만족을 하고 결과값도 87이 되는 것을 확인할 수 있었습니다. 

 

#코드

해당 문제는 직관적으로 느껴지는 알고리즘으로 문제를 풀면 시간 초과를 발생시킵니다. 시간 초과와 관련한 시간 복잡도는 다음 글에서 다뤄보도록 하겠습니다. 

 

먼저 저도 직관적으로 알고리즘을 설정하고 문제를 풀어봤었는데요.. 시간 초과 코드는 더보기에 추가해 두겠습니다. 

#include<stdio.h>

int main() {

int N = 0; // 입력받는 N
int sum = 0;
int ans = 0;
int current_sum = 0;

scanf("%d", &N);
int number[N];


for(int j = 1; j <= N; j++) {
    current_sum = 0;
    for(int i = 1; i <= j; i++) { 
    number[i-1] = i;
    if(j % number[i-1] == 0){
        current_sum = current_sum + number[i-1];
    }
}

sum = current_sum + sum;

}

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

    return 0;
}

 

 

기본 개념에서 언급한 숫자들의 규칙성을 코드로 잘 표현하는 것이 중요하겠습니다. N보다 같거나 작은 자연수들을 i라고 했을 때, ans = ans + ( N / i ) * i 는 N보다 같거나 작은 자연수들의 약수들의 합이 됩니다.   

 

#include<stdio.h>

int main() {
    int N; // 입력되는 N
    long long ans = 0;

    scanf("%d", &N);

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

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

    return 0;

}