[C]백준 Q.17425 약수의 합 1

https://www.acmicpc.net/problem/17425

 

이어서 ~ 

이전의 약수의 합2에서 다음문제인 약수의 합1...

왜 문제집에서 순서를 반대로 푸나 했는데 막상 풀어보니 아 이래서 그랬구나 했다

약수의 합 2에서 미리 약수의 합값을 전부 계산해둔다음 필요한 부분을 더해서 출력하는 과정을 거쳤는데

이번 1은 그걸 더 반복적으로 요구한다

 

아무생각없이 그냥 2의 소스를 그대로 복붙해서 입력 받는 부분만 바꿨더니 바로 시간초과...

아차! 매 입력마다 약수합부분을 새로 구하는구나 해서 해당부분을 분리 ~ 시간초과...

fx값을 누적값은 중간까지 바뀌지않으니 괜히 처음부터 하면 안되는구나 싶어서 또 해당 부분을 분리 ...

뭐 이런 과정을 거쳐서 아래 소스

#include <stdio.h>
/**
 q17425 약수의합
 */


#define MAX 1000000

long long f[MAX + 1];
long long g[MAX + 1];

long long solution(long n) {
    // f[1] ~ f[n] 까지의 합
    long long g = 0;
    for (int i = 1; i <= n; i++) {
        g += f[i];
    }
    return g;
}

void setupEratos(long max) {
    // 각 i의 배수들의 합을 f배열에 저장
    for (int i = 1; i <= max; i ++) {
        for (int j = i; j <= max; j += i) {
            f[j] += i;
        }
    }
}

void setupSumArray(long max) {
    // g값을 미리 전부 계산
    for (int i = 1; i <= max; i++) {
        g[i] = g[i - 1] + f[i];
    }
}

int main(int argc, const char * argv[]) {
    long t;
    
    while (scanf("%ld", &t) == 1) {
        long nValues[100000] = {0};
        long max = 0;
        
        for (int i = 0; i < t; i ++) {
            scanf("%ld", &nValues[i]);
            if (nValues[i] > max) {
                max = nValues[i];
            }
        }
        
        // fx값 미리계산
        setupEratos(max);
        
        // gx값 미리계산
        setupSumArray(max);
        
        // 결과 출력
        for (int i = 0; i < t; i ++)
            printf("%lld\n", g[nValues[i]]);
    }
    
    return 0;
}

솔루션은... 저렇게 빼는게 오히려 이상해보이는데 

약수의 합2의 소스의 흔적이다;;

통과하니 괜히 바꾸기 귀찮

 

https://github.com/wiwi-git/c-baekjoon

GitHub - wiwi-git/c-baekjoon: 블로그 업데이트용 백준 코드