[백준] code.plus(수학,JAVA)17425번, 약수의 합

문제 링크

17425번: 약수의 합

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제를 접근할 때 아래 링크의 문제와 매우 비슷하여 거의 동일한 알고리즘을 사용하였더니 시간초과가 발생하였습니다.

[백준] code.plus(수학,JAVA)17427번, 약수의 합 2

이전 문제에서는 입력값이 단일 값으로 한 번만 연산하여 결과를 출력하였다면 여기서는 여러번 반복하여 연산을 진행한 뒤에 결과를 출력하는 것으로 시간초과가 발생한다는 것으로 파악하였습니다.

 

그래서 사용한 방법은 미리 모든 f(x)와 g(x)을 구해놓고 입력되는 값에 해당하는 값을 반환하는 것으로 하였습니다.

 

모든 f(x)와 g(x)의 값을 저장하기 위해 배열을 입력값의 최대값의 크기만큼 만들었습니다.

 

f(x)값을 저장할 때에 약수 1을 가지기 때문에 모든 값을 1로 바꾸도록 Arrays.fill()을 사용하였습니다.

 

2의 배수는 모두 2의 약수를 가지고 있는 것으로 2의 배수에 해당하는 배열 인덱스는 모두 2를 더하였고 3의 배수도 동일하게 3의 약수를 가지고 있는 것으로 해당하는 배열 인덱스에 모두 3을 더하는 것을 반복하였습니다.

 

위에 과정을 반복하여 f(x)를 누적합 방식으로 배열을 완성하였습니다.

 

g(x) = g(x-1) + f(x)으로 표현할 수 있으며 g(1) = 1이므로 공식을 반복하여 g(x) 배열에 값들도 완성하였습니다.

 

이후 입력되는 값들에 대하여 배열에 있는 값을 그대로 가져와서 출력하도록 하였습니다.

 

문제에 해결알고리즘은

1. f(x)와 g(x)를 저장할 정수형 배열[1000001] 2개를 만들었습니다.

2. f(x)는 배수는 약수라는 것을 이용하여 반복문을 통해 누적합 방식으로 배열을 완성시켰습니다.

3. g(x) = g(x-1) + f(x), g(1) = 1 두 식을 이용하여 반복문을 통해 배열을 완성시켰습니다.

4. 입력값을 받은 후 g(x)배열에서 그 값에 해당하는 값을 가져와 출력하도록 하였습니다.

 

• f(x)와 g(x)의 값을 저장하는 배열[1000001]을 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• Arrays.fill()을 사용하여 f(x)의 배열을 1로 초기화하였습니다.
• f(x)를 계산하는 fxCal함수를 만들었습니다.
• f(x)는 함수를 이용하고 g(x)는 공식을 이용하여 완성시켰습니다.
• BufferedWriter에 입력값에 따른 g(x)에 배열에 값을 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• fxCal에서는 배수는 약수도 될 수 있다는 것을 반복문과 누적합으로 f(x) 배열을 완성시켰습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int maxNum = 1000001;	//입력 최대값
	static long[] fx = new long[maxNum];	//f(x) 값 배열
	static long[] gx = new long[maxNum];	//g(x) 값 배열
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        Arrays.fill(fx, 1);		//f(x)를 모두 1로 초기화
        gx[1] = 1;		//g(x) = 1
        for(int i=2;i<maxNum;i++) 	//f(x) 배열 완성시키기
        	fxCal(i);
        
        for(int i=2;i<maxNum;i++) 	//g(x) 배열 완성시키기
        	gx[i] = gx[i-1] + fx[i];
        
        //----입력값에 대응하는 g(x)값 BufferedWriter 저장-------
        int T = Integer.parseInt(br.readLine());
        for(int i=0;i<T;i++) {
        	int num = Integer.parseInt(br.readLine());
        	bw.write(gx[num] + "\n");   	
        }
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //--------f(x)구하는 함수--------
    public static void fxCal(int n) {
    	int i=1;
        /* 배수이면 약수
        예를 들어 2의 배수이면 2의 약수를 가진 것으로
        2의 배수의 인덱스를 가진 f(x)의 배열은 모두 +2를 해줍니다.
        위 과정을 반복*/
    	while(i*n<maxNum) {
    		fx[i*n] += n;	
    		i++;
    	}
    }
}