백준 17427번: 약수의합2(JAVA)

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

17427번: 약수의 합 2

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		long sum = 0;
		for(int n = 1; n <= N; n++) {
			sum += (N/n) * n;
		}
		
		System.out.println(sum);
		
	}
}

 

[풀이]

f(y)의 시간복잡도는 O(N). (혹은 O(√N)).

모든 자연수 y의 f(y)값을 더한 값인 g(x)의 시간 복잡도는 N*O(N).

N의 범위가 1,000,000 이므로, 단순히 약수 구하는 방법으로는 이 문제를 풀 수 없다.

 

N = 6 이라고 하면,

N	1	2	3	4	5	6
약수	1	1, 2	1, 3	1, 2, 4	1, 5	1, 2, 3, 6

(1) + (1+2) + (1+3) + (1+2+4) + (1+5) + (1+2+3+6) 을 구해야 한다.

 

약수의 반대인 '배수'를 이용해 문제를 풀어볼 수 있다.

"n의 배수" = "n을 약수로 갖는 수"

 

따라서,

N 이하의 자연수 중 1의 배수: N/1개

N 이하의 자연수 중 2의 배수: N/2개

...