[백준 BOJ] 17425번: 약수의 합

📌 참고

교공 알고리즘 스터디에서 다룬 문제는 19주차부터 벨로그에 기록하고 있습니다 (18주차 이전 문제들을 추후 복습 겸 업로드할 계획도 있습니다 🤗) 그 외 개인적으로 풀어본 백준 및 프로그래머스 문제는 스스로 유의미하다고 여겨진 부분들이 있는 문제만 선별하여 벨로그에 기록하고 있습니다 벨로그에 올라오지 않은 다른 문제와 코드가 궁금하신 분들은 아래의 github에서 추가로 확인하실 수 있습니다 👀 방문해주셔서 감사합니다 🙏

💚 github | dianstar/Algorithm-BOJ
💚 github | dianestar/Algorithm-Programmers

code.plus 문제집 : 코딩 테스트 준비 - 기초 | 수학

17425번: 약수의 합 | 문제 바로가기

문제풀이 (2022-02-03 THU 💻)

⭐ 풀이의 핵심

어제 풀었던 17427번: 약수의 합 2 문제랑 똑같은 문제인데
입력으로 숫자 하나만 받는 것이 아니라
T(1<=T<=100,000)개의 테스트케이스를 받기 때문에
17427번과 똑같은 방법으로 풀면 또 시간초과가 발생한다

따라서 Dynamic Programming 의 방법으
주어지는 자연수 N의 범위인 N=1부터 N=1,000,000까지의 모든 g(N) 값을 구해놓은 후
입력 받는대로 해당 값을 출력 해주는 방식을 택해야 한다

🔽 코드 (C++)

#include <iostream>
using namespace std;

#define MAX_NUM 1000001

int arr[MAX_NUM]; // arr[A]: f(A)의 값, 즉 A의 모든 약수를 더한 값
long long sum[MAX_NUM]; // sum[x]: g(x)의 값, 즉 x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값

int main() {
    for (int i=1; i<MAX_NUM; i++) {
        for (int j=1; i*j<MAX_NUM; j++) {
            arr[i*j] += i;
        }
    }
    
    sum[1] = arr[1];
    for (int i=2; i<MAX_NUM; i++) {
        sum[i] = sum[i-1] + arr[i];
    }

    int T;
    scanf("%d", &T);

    int N;
    for (int i=0; i<T; i++) {
        scanf("%d", &N);
        printf("%lld\n", sum[N]);
    }
    
    return 0;
}