[백준 / C언어] Day32. 약수의 합 2 (17427)

2024. 07. 05 - 코딩테스트 스터디 Day32

 

 

01. 문제

두 자연수 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)로 표현한다.

자연수 N이 주어졌을 때, g(N)을 구해보자.

 

 

02. 입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

 

 

03. 출력

첫째 줄에 g(N)를 출력한다.

 

 

04-1. 예제 입력 1

1

 

 

04-2. 예제 출력 1

1

 

 

05-1. 예제 입력 2

2

 

 

05-2. 예제 출력 2

4

 

 

06-1. 예제 입력 3

10

 

 

06-2. 예제 출력 3

87

 

07-1. 예제 입력 4

70

 

 

07-2. 예제 출력 4

4065

 

 

08-1. 예제 입력 5

10000

 

 

08-2. 예제 출력 5

82256014

 

 

 

09-1. 1차 풀이 - 시간초과

우선 이 문제는 n의 값을 입력받은 뒤, n보다 작거나 같은 모든 자연수의 약수의 합을 구하는 문제이다.

 

예를들어, n이 3이라면 
f(1) + f(2) + f(3) = 1 + 1 + 2 + 1 + 3 = 8
이므로 8이 되는 것이다.

 

#include <stdio.h>

int main() {
    int n;
    long long answer = 0;
    scanf("%d", &n);
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i % j == 0) {
                answer += j;
            }
        }
    }
    printf("%lld\n", answer);
        
    return 0;
}

우선 이중 for문을 사용하여 1부터 n까지의 자연수의 약수를 찾아 answer 변수에 저장하도록 코드를 짜보았다.

 

 

그러나 시간 초과가 떴다.

이래저래 더 시도해 봤는데 해결 방법을 찾지 못해서 서치를 해보았다.

 

09-2. 2차 풀이 - 정답

서치를 통해 새로운 풀이 방법을 알게 되었다.

 

우선 n이 10이라면,
f(1) = 1
f(2) = 1 + 2
f(3) = 1 + 3
f(4) = 1 + 2 + 4
f(5) = 1 + 5
f(6) = 1 + 2 + 3 + 6
f(7) = 1 + 7
f(8) = 1 + 2 + 4 + 8
f(9) = 1 + 3 + 9
f(10) = 1 + 2 + 5 + 10
위와 같이 계산될 것이다.

이때, 약수들을 잘 살펴보면
f(1)부터 f(10)까지 포함된
1의 개수: 10개 (10을 1로 나눈 몫)
2의 개수: 5개 (10을 2로 나눈 몫)
3의 개수: 3개 (10을 3으로 나눈 몫)
4의 개수: 2개 (10을 4로 나눈 몫)
5의 개수: 2개 (10을 5로 나눈 몫)
6의 개수: 1개 (10을 6으로 나눈 몫)
7의 개수: 1개 (10을 7로 나눈 몫)
8의 개수: 1개 (10을 8로 나눈 몫)
9의 개수: 1개 (10을 9로 나눈 몫)
10의 개수: 1개 (10을 10으로 나눈 몫)
이라는 것을 알 수 있다.

 

#include <stdio.h>

int main() {
    int n;
    long long answer = 0;
    
    scanf ("%d", &n);
    
    for (int i = 1; i <= n; i++) {
        answer += (n / i) * i;
    }
    
    printf("%lld\n", answer);
    
    return 0;
}

위의 풀이과정을 이용하여 코드를 작성해 보았다.

 

i가 1부터 입력받은 n이 될 때까지 반복문을 돌면서 n을 i값으로 나눈 뒤, i를 곱한 값을 answer에 저장해 주면 된다.

이렇게 하면 시간 복잡도가 O(n)이 되어, 시간 초과가 뜨지 않는다!

 

정답!

 

---

어렵다!

 

 

참고한 게시글

https://nanyoungkim.tistory.com/28

[C++]백준 17427번 - 약수의 합 2