[JAVA]백준 17427 - 약수의 합2

문제

두 자연수 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)을 구해보자.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 g(N)를 출력한다.

예제입력 / 예제출력

1                  /         1

2                 /         4

10               /         87

10000        /      82256014

문제 풀이 전 이론 - 1

- 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다.

- A의 약수인 C를 구하기 위해선 A를 1~A만큼 모두 나누었을 때 나머지가 0이되는 값이 약수이다. 따라서, 실행 시간이 O(A) 즉, O(N)이다.

- 하지만 본 문제처럼 시간 제한이 있는 경우에는 O(N)이 치명적일 수 있다. 왜냐하면, N이 최대 1,000,000으로 주어졌기 때문이다. 

- 따라서 약수를 구하는 시간을 줄여보아야 한다.

문제 풀이 전 이론 -2

- 약수를 구하는 실행 시간은 O($ \sqrt{N} $)으로 줄일 수 있다.

- 이론 -1에서 C는 A의 약수라고 하였다. 그러면 A/C또한 A의 약수여야 한다. 예를 들어

- 24의 약수 1,2,3,4,6,8,12,24가 있으면 24/12 = 2로 약수이고 24/8 = 3로 약수이기  때문이다.(양 끝값을 곱하면 A가 된다는 원리)

- 그러면 A/C=C (A/C는 약수)이기 때문에 A = $C^2$ 이므로, C = $ \sqrt{A} $이 된다. 

- 즉, 우리는 굳이 A를 1~A만큼 모두 나누어 O(A)라는 시간이 걸리지 않아도

- 중간 값($ \sqrt{A} $)만 알아도 모든 약수들을 구할 수 있다. 그래서 O($ \sqrt{A} $)로도 약수를 구할 수 있다.

문제 풀이 전 이론 - 3

- 그럼 실행 시간을 예측해보겠다. 문제를 보기 쉽게 나타내보면

- f(A) = 약수의 합

  g(x) = f(1) + ... + f(A)

  g(N) = f(1) + ... + f(N)

- 따라서 f(N)이라고 치면, f(N)의 모든 약수를 구함과 동시에 덧셈을 하므로, O(N)이거나 O($ \sqrt{N} $)이 된다.

- 하지만 우리는 "g(N) = N이하의 모든 자연수들의 약수의 합"을 구해야 하므로 N만큼의 시간이 더 걸린다.

- 따라서 O($N^2)이거나 O($N \sqrt{N} $)이 된다.

- 하지만, 문제에서는 0.5초라는 제한 시간이 걸려 있어서 위의 big O notation이 제한 시간 안에 실행되는지 살펴보아야 한다.

- 1억을 1초라고 가정하고 N의 최악은 100만이므로

- O($N^2$) = $1,000,000^2$ = 1초 = 10000초

- O($ N\sqrt{N} $) = 1,000,000 * 1,000 = 10억 = 10초

- 둘다 0.5초를 훨씬 웃돈다.. 어떻게 해야할까?..(위의 이론들이 쓸모 없어졌지만 위의 이론을 알지 못했다면 이만큼 도달하지도 못했다.) 

문제 풀이

- 이럴 때에는 약수의 반대 개념인 배수로 풀어야 한다(핵심 아이디어).

- 3의 배수 = 3,6,9,12,15,18,... 이다.

- 다른 말로, "3의 배수 = 3을 약수로 갖는 수의 집합"(핵심 아이디어)이다.

- 더 쉽게 이해하면, "3의 배수를 알면 약수 3을 가진 값들을 알 수 있다는 것이다"(핵심 아이디어)

- 위의 이론을 이 문제에 적용해보면 어떨까?

- N을 7이라고 가정하면 g(7) = f(1) + ... + f(7)이다. 즉, 7 이하 자연수들의 약수의 합이된다.

- 우리는 위의 방법을 알기 때문에 각각 f(1)...f(7)을 따로따로 약수를 구해서 더한 다음에.. 그걸 또 다 더할 필요가 없다.

- 그냥, 1~7까지 자연수 중에서 약수 1을 가진 값은 무엇일까(몇개일까)?

- 1~7까지 자연수 중에서 약수 2을 가진 값은 무엇일까(몇개일까)?

 ....

- 1~7까지 자연수 중에서 약수 7을 가진 값은 무엇일까(몇개일까)?를 계산해보면 되는 것이다. 수식은 아래와 같다.

- 1~7까지 자연수 중에서 7의 배수의 개수 = 약수 7을 가진 값들의 개수 = 7을 약수로 갖는 값의 개수 = ⌊N/7⌋이다.

- 이렇게 1~7까지 자연수 들의 배수의 개수를 구해보면

- ⌊N/1⌋ = 7 , ⌊N/2⌋= 3, ⌊N/3⌋ = 2,⌊N/4⌋ = 1,⌊N/5⌋ = 1,⌊N/6⌋ = 1,⌊N/7⌋ = 1개이다.

- 실제로 그런지 한 번 보자

 

- 정말 약수 1의 개수는 7개, 약수 2의 개수는 3개로 모두 다 들어맞는다.

- 자, 하지만 여기서 끝내면 절때 안된다. 우리는 이 약수들의 합을 구해야 했다는걸 잊어선 안된다!

- 1로 예를 들면, 1 X (1의 개수)가 될테니 

- 1X⌊N/1⌋ = 7, 2X⌊N/2⌋= 6, 3X⌊N/3⌋ = 6, 4X⌊N/4⌋ =4, 5X⌊N/5⌋ = 5, 6X⌊N/6⌋ =6, 7X⌊N/7⌋ =7

- 이 값들을 싹다 더해주면 끝이다. 결과적으로 O(N)이라는 훨씬 짧은 시간으로 단축할 수 있게 됐다.

- 이제 소스 코드를 보자.

소스 코드

public class Main {
	public static void main(String[] args) {
		int N;
		long res = 0; // 1000000까지 입력할 것을 고려
		
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		
		for(int i = 1; i <= N; i++) {
			res += i * (N/i);
		}
		System.out.println(res);
	}
}

출력

문제로부터 얻어간 것

- 이론 -1, 이론 -2, 이론 -3에 대한 정보를 알게됐다.

- 미리 실행시간을 예측하는 것이 얼마나 중요한 것인지 알게됐다.

- 효율성 문제는 최대한 많이 풀어서 폭 넓은 사고를 할 수 있어야 한다.

느낀점

이러한 효율성 문제가 만약 문제로 나온다면 잘 풀 수 있을지 모르겠다. 사실, 효율성을 따진다면 우리가 알고있는 기본적인 코드 상식으로는 풀 수 없고 더 좋은 방향을 알아내야 하는 것인데, 내가 알고있는 배경 지식에 따라, 그 날의 컨디션에 따라서 해결할 수도 못할 수도 있다고 생각한다. 일단 우리는 이 문제를 공부했으니 이 문제가 나온다면 풀 수 있을 것이고 더욱 많은 문제를 풀어서 대비해야겠다.