[백준 / C언어] Day33. 약수의 합 (17425)

2024. 07. 06 - 코딩테스트 스터디 Day33

 

 

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. 입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 둘째 줄부터 테스트 케이스가 한 줄에 하나씩 주어지며 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

 

 

03. 출력

각각의 테스트 케이스마다, 한 줄에 하나씩 g(N)를 출력한다.

 

 

04-1. 예제 입력 1

5
1
2
10
70
10000

 

 

04-2. 예제 출력 1

1
4
87
4065
82256014

 

 

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

우선 이 문제는 어제 풀었던 '약수의 합(17427)' 문제와 거의 유사해보인다.

다른 점이라면, 테스트 케이스의 개수를 입력받아 그 개수만큼 g(N)을 출력한다는 점이다.

 

#include <stdio.h>

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

우선 처음으로 시도해 본 코드이다.

어제 코드에서 테스트 케이스의 개수를 받아 그만큼 반복문을 돌면서 테스트 케이스를 입력받는 부분만 추가되었다.

 

 

그러나 역시 오늘도 시간 초과가 떴다.

테스트 케이스 개수만큼 돌리는 for문이 추가되었기 때문에 제한시간을 넘기게 되는 것으로 예상된다.

 

05-2. 2차 풀이 - 정답

이런저런 시도를 해보다가 결국 올바른 방법이 떠오르지 않아 서치를 해보게 되었다.

 

우선 매 테스트 케이스마다 새로 f(n)을 계산하게 되어, 같은 계산을 중복하게 되는 경우가 생긴다.
예를 들어,

g(3) = f(1) + f(2) + f(3)
g(5) = f(1) + f(2) + f(3) + f(4) + f(5)

위 두 케이스는 겹치는 부분이 존재한다!

매번 새로 계산하는 것은 비효율적이기 때문에,

f(1)부터 f(1000000)까지의 수를 모두 계산해 둔 뒤, 입력받은 n값에 따라 g(n)을 계산하는 방법을 사용하고자 한다.

 

#include <stdio.h>

#define MAX_SIZE 1000000

int main() {
    int t, n;
    long long answer[MAX_SIZE + 1] = {0};
    
    for (int i = 1; i <= MAX_SIZE; i++) {
        for (int j = 1; i * j <= MAX_SIZE; j++) {
            answer[i * j] += i;
        }
        answer[i] += answer[i - 1];
    }
    
    scanf("%d", &t);
    
    for (int i = 0; i < t; i++) {
        scanf("%d", &n);

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

i가 1부터 1000000이 될 때까지 반복문을 돌면서, 인덱스가 i를 약수로 가진 수일 때, 해당 배열에 i값을 더해준다.

이렇게 하면 f(1)부터 f(1000000)의 값을 모두 구할 수 있다.

 

그 뒤, 테스트 케이스의 개수인 t를 입력받고, t만큼 반복문을 돌면서, n을 입력받고, answer[n], 즉 g(n) 값을 출력해 주면 된다.

 

정답!

 

---

서치를 해보지 않았다면 생각해내지 못했을 풀이 방법인 것 같다.

공부를 더 열심히 해야 할 것 같다 ㅎㅎ

 

 

참고한 게시글

https://csloth.tistory.com/20

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