[백준] 17425번: 약수의 합 - JAVA

dev-jjun·2023년 1월 18일

boj 알고리즘

코딩테스트 준비

목록 보기

7/11

🔗 문제

BOJ 17425 : 약수의 합

난이도 - 골드 4

알고리즘 분류 - 수학, 정수론, 누적 합, 소수 판정, 에라토스테네스의 체

💬 풀이

A와 B 두 수가 있다고 하자. A=BC를 만족하는 자연수 C가 A의 약수로 정의되므로, A=24에서 약수 1,2,3,4,6,8,12,24 를 모두 더한 60을 f(A)라고 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y) 값을 더한 값은 g(x)로 표현한다. 예를 들어 x=10일 때, 1~10까지 각각의 약수를 모두 구해서 1의 약수합 + 2의 약수합 +... + 10의 약수 합까지 모두 더한 값이 g(x)가 되는 것이다.

입력값이 주어질 때마다 그때그때 약수합을 일일이 구하기에는 같은 과정이 계속해서 반복되므로 비효율적이다. 이때는 입력으로 가능한 범위에서의 값을 미리 계산해둔 후에 이를 배열에 저장해서 값을 꺼내오는 방식으로 구현하는 것이 좋은 솔루션이다.

자연수 N의 범위는 1,000,000까지이므로, 1,000,001 크기의 배열을 f(x), g(x)를 나타내기 위해 선언한다.
약수라는 수학적 성질에 따라 1부터 반복문을 돌며 나누어 떨어지는 수에서 해당 인덱스의 값에 더해나가는 방식으로 1~1,000,000의 약수 합을 배열에서 바로 구하고 저장한다.

f(x)

반복문에서 사용한 반복인자 i, j로 표현하자면 ij=x 라는 수식이 있을 때, x의 최대 약수는 ij이다.
따라서 반복문도 i*j까지만 돌면 된다. 모든 자연수의 공통 약수인 1을 반복문을 돌기 전에 Arrays의 fill() 메서드로 미리 채워준 후, 2부터 반복문을 돌며 나누어 떨어지는 수에 해당하는 경우만 값을 더해준다.

g(x)

f(x)에 모든 자연수에서의 약수 합을 구해두었으니 그 바로 전의 인덱스가 가진 값이 해당하는 자연수 이하의 약수 총합이므로 f(x)를 구한 후에 g(x)를 구성해준다.

💻 코드

package Baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class _17425 {

    final static int MAX = 1000001;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        long[] fx = new long[MAX];   // f(x) : 각 자연수의 모든 약수를 더한 값 저장
        long[] gx = new long[MAX];   // g(x) : 해당 자연수 이하의 모든 f(x)값을 더한 값 저장

        Arrays.fill(fx, 1);   // 모든 자연수는 1을 약수로 가지므로 1로 채워준다.

        for (int i=2; i<MAX; i++) {
            for (int j=1; i*j<MAX; j++) {  // i*j의 약수 x에 대하여 범위는 i*j (곱이 최대 약수)으로 제한
                fx[i*j] += i;
            }
        }

        for (int i=1; i<MAX; i++) {
            gx[i] = gx[i-1] + fx[i];   // f(x)을 차례로 더하여 (x 이하의 값에서의 약수 합) g(x) 계산
        }

        int T = Integer.parseInt(br.readLine());

        for (int i=0; i<T; i++) {
            sb.append(gx[Integer.parseInt(br.readLine())] + "\n");
        }
        System.out.println(sb);
    }

}