[백준] 17425 약수의 합2 (Java)

✉️문제

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

17427번: 약수의 합 2

 

📝 접근

1. 테스트 케이스가 여러개이므로 미리 배열에 값들을 저장해 놓아야 한다.

// f(A)를 구하는 과정
for(int i = 1; i < SIZE; i++) {
    for(int j = i; j < SIZE; j = j + i) {
        arr[j] += i;
    }
}

// g(A) 구하기
for(int i = 1; i < SIZE; i++) {
    answer[i] = answer[i-1] + arr[i];
}

 

2. 출력이 많아질 수 있으므로 BufferedWriter를 사용하는 것이 좋다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

 

🗝 문제풀이

package divisor;

import java.io.*;
import java.util.Scanner;

public class B17425RRR {

    static final int SIZE = 1000001;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        long[] arr = new long[SIZE];
        long[] answer = new long[SIZE];

        // f(A)를 구하는 과정
        for(int i = 1; i < SIZE; i++) {
            for(int j = i; j < SIZE; j = j + i) {
                arr[j] += i;
            }
        }

        // g(A) 구하기
        for(int i = 1; i < SIZE; i++) {
            answer[i] = answer[i-1] + arr[i];
        }

        int n = Integer.parseInt(br.readLine());
        while(n-- > 0) {
            int input = Integer.parseInt(br.readLine());
            bw.write(answer[input] + "\n");
        }

        bw.flush();
    }
}