[JAVA]백준 17425 - 약수의 합

문제

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.

자연수 N이 주어졌을 때, g(N)을 구해보자.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 둘째 줄부터 테스트 케이스가 한 줄에 하나씩 주어지며 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

각각의 테스트 케이스마다, 한 줄에 하나씩 g(N)를 출력한다.

예제입력 / 예제출력

5              

1              /  1

2                 4

10               87

70               4065

10000        82256014

 

문제 풀이 전 이론 - 1

- 이 문제는 직 전에 포스팅한 [백준 17427 - 약수의 합2] 문제와 동일한 핵심 아이디어를 사용한다.

- 핵심 아이디어는 약수의 반대인 배수 개념을 이용하는 것이다.

- 배수의 개념을 사용하면 특정 약수를 가지고 있는 값들을 알 수 있으며, 해당 값의 개수 = 약수의 개수가 될 수 있다.

 

문제 풀이

- 배수의 개념을 통하여 약수(i)를 가지고 있는 값(배수)를 구하고, 그 배수에 약수들을 누적하여 더해주어야 한다.

- 특정 약수(i)를 가지고 있는 값(배수)를 구하기 위해서는 (1~N)까지 곱해주어야 한다. ex) 1(i) x 1(j) = 1 , 1(i) x 2(j) = 2, 1(i) x 3(j) = 3

- 일단 모든 N은 약수 1을 포함하고 있기 때문에 반복문을 돌려서 인덱스에 1을 할당시킨다.

- 그다음 약수 2부터 1...N을 곱해주어 약수 2를 가지고 있는 값(배수)를 구하고, 그 배수 값에 약수를 누적하여 더해준다.

- 그러면 약수는 자기 자신을 약수로 갖는 값(배수) 자리에 쏙쏙 들어가서 더해짐으로써 f(N)이 만들어질 것이다.

- 주의해야 할 것은 곱셈한 값은 N보다 작거나 같아야한다.

- 해당 문제는 실행시간이 1초로 한정되어 있다.

-  [백준 17427 - 약수의 합2] 문제에서는 O(N)으로 합을 구했기 때문에 실행시간이 단축되었지만,

- 이 문제는 "테스트 케이스"개념이 들어가서 여러번 입력을 시켜야 한다.

- '[백준 17427 - 약수의 합2] 문제에 반복문을 덮어서 원하는 만큼 반복 실행하면 되는 것 아닐까?'라고 생각할 수 있다. 하지만 

- 입력 횟수는 최대 100,000번(T)이기 때문에 10만번 반복하면서 100만번 계산해야 하므로 = 1000억 = 1000초가 된다. = O(TN)

- 따라서 "테스트 케이스"개념으로 인한 효율성 문제를 해결하기 위해 "계산된 값을 배열에 미리 저장해놓는 아이디어"를 사용한다.

 

소스 코드

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

public class Main {
	static final int MAX = 1000000; // N은 최악의 경우, 최대 100만까지

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		long v[];
		long sum[];
		
		v = new long[MAX+1]; // 최악의 경우인 100만을 모두 담는 배열로, f(1...N)값이 들어간다
		sum = new long[MAX+1]; // 최악의 경우인 100만을 모두 담는 배열로, g(1...N)값이 들어간다.
              // 즉, 덧셈이 누적된 값이 들어간다.
		
		for(int i = 1; i <= MAX; i++) { // 1...N은 모두 1을 약수로 포함하고 있다.
			v[i] = 1;
		}
		
		for(int i = 2; i <= MAX; i++) { // 1은 약수 1밖에 없으므로 2부터 시작
			for(int j = 1; j*i <= MAX; j++) { // 배수 = i를 약수로 갖고있는 값
            			//만약 약수(i)가 2라면, 2의 배수인 2 4 6...이 약수(i) 2를 가지고 있다.
                              //배수 값들을 구하기 위해 약수를 1부터 곱해준다. 
				v[j*i] += i; //그럼 각 인덱스에 약수들이 더해져서 f(1...N)이 될 것이다.
			}
		}
		
		for(int i = 1; i <= MAX; i++){
			sum[i] = sum[i-1] + (int)v[i]; // f(1...N)을 누적하여 덧셈한 값을 sum의 각 인덱스에 할당한다.
                  // 이전 누적 값 + 현재 값
		}
                 //이제 sum[]에 모든 g(1...N)값들이 들어가 있다.
                 //따라서 마지막에 원하는 만큼 반복(t)해서 원하는 N값을 입력하여 g(N)을 출력한다.
		
		int t = Integer.parseInt(bf.readLine());
		while(t--> 0) {
			int n = Integer.parseInt(bf.readLine());
			bw.write(sum[n]+"\n");
		}
		
		bw.flush();//buffer에 저장했다가 한번에 stream에 나타낸다.
		
	}

}

- 다른 반복문들은 N이니까 상관 없고, 배수 아이디어를 사용한 이중 FOR문이 O($N^2$)이냐 아니냐를 봐야한다.

- 일단 쉽게 생각하면, i =2 이면 j는 1~3이다. i=3 이면 j는 1~2이다. i=4 이면 j는 1이다. 즉, j는 O(N)이 아니기 때문에 O($N^2$)은 아니다.

- 자세히 구해보면, j는 j*i <= MAX까지 반복하므로 j = $N/i$로 $N/2,N/3,N/4,....N/N$이다.

- 이는 곧 1/2,1/3,1/4,...1/n <= ln(n)+1이기 때문에, 시간복잡도는 O(nlgn)이다. 

출력

문제로부터 얻어간 것

- 어떠한 기능을 반복하여 입력하여 출력하는 "테스트 케이스"문제는, 사실 전체 코드를 반복문으로 감싸주면 되지만 시간 복잡도 상으로는 N번을 곱해주는 것이기 때문에 효율적인 측면에서 문제가 발생한다. 따라서, 최악의 경우만큼 배열을 할당하고, 그 배열의 인덱스에 정답들을 모두 넣어놨다가, 입출력을 반복해야 한다.

느낀점

- 미리 저장해놨다가 출력하는 방법은 효율적인 측면으로 꽤 큰 퍼포먼스를 보이기 때문에 잘 활용할 수 있을 것 같다. 하지만 너무 무리하게 할당시켰다가는 자칫 Out Of Memory가 발생할 수도 있으니, 효율성을 따지는 문제에서만 사용해야겠다.

 

- 약수 문제는 그냥 무조건 배수 개념으로 접근하는 것이 효율적일 것 같다.