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

문제 링크

17427번: 약수의 합 2

---

주의사항

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

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

---

문제 설명

---

접근 방법

처음 문제를 작성할 때에는 반복문을 2번 사용해서 각 숫자에 대하여 약수를 구하여 더하는 형식으로 진행하였으나 시간복잡도가 n²으로 시간초과가 발생하였습니다.

그래서 약수를 구하는 다른 방법이 있나 끄적여보다가 규칙을 발견하게 되었습니다.

만약 입력값이 6일 때 약수를 나타내는 표를 만들어보겠습니다.

1	1
2	1	2
3	1		3
4	1	2		4
5	1				5
6	1	2	3			6

위에 표에서 파란색 숫자는 빨간색 글자에 해당하는 약수입니다.

개수를 살펴보면 1 = 6개, 2 = 3개, 3 = 2개, 4 = 1개, 5 = 1개, 6 = 1개 입니다.

1 = 6/1개 2 = 6/2개 3 = 6/3개 4 = 6/4개 5 = 6/5개 6 = 6/6개로 규칙을 가질 수 있습니다.

이 규칙을 이용하여 해결 알고리즘을 작성해보겠습니다.

해결 알고리즘은

1. 입력값보다 작거나 같은 수들을 입력값에 나누어 몫을 구합니다.

 

2. 몫은 약수의 개수이므로 개수 * 약수의 숫자를 모두 더해줍니다.

 

3. 모두 더해진 결과를 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• g(x)를 구하는 g함수를 만들었습니다.
• 함수를 실행 후 BufferedWriter에 g(x)의 결과값을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• g에서는 반복문을 통해 위에 해결 알고리즘대로 설계하여 작성하였습니다.

 

결과 코드

import java.io.*;
public class Main{
    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));
        //결과값 출력하는 BufferedWrtier
        //입력값 저장 및 함수 실행---------
        int num = Integer.parseInt(br.readLine());
        long result = g(num); 
        bw.write(result + "\n");	//결과 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //--------g(x) 구하는 함수---------
    public static long g(int n) {
    	long result = n;	//1의 약수는 n의 수만큼 있으므로 n으로 초기화
    	for(int i=2;i<=n;i++) {
    		result += (n/i) * i;	//나눈 몫의 나눈 값을 곱함
    	}
    	return result;	//결과 반환
    }
}