[Baekjoon] 17427 약수의 합 2 (S2^ / 수학) - Java

링크

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

17427번: 약수의 합 2

 

 

 

문제 해석

자연수 N이 주어졌을 때, 1부터 N까지 각각의 수가 가지는 자연수의 합을 구하는 문제입니다.

 

ex) N = 3

1) 1의 약수 = 1

2) 2의 약수 = 1, 2

3) 3의 약수 = 1, 3

-> 정답은 "1 + 1 + 2 + 1 + 3 = 8" 이 나옵니다.

 

 

 

코드

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());

		long sum = 0L;

		for (int i = 1; i <= N; i++) {
			sum = sum + N / i * i;
		}

		System.out.println(sum);
	}
}

 

 

 

코드 해석

N의 최대 범위가 1,000,000이므로 각 숫자에 대해서 순차적으로 약수를 구하려고 하면 시간 초과가 날 수 밖에 없습니다.

 

따라서 이를 해결할 방법이 필요합니다.

 

 

N = 5일 때를 예를 들자면,

 

1, 2, 3, 4, 5의 약수를 구해야 합니다.

 

일반적으로 A라는 하나의 숫자의 약수는, A를 1부터 A까지 나누면서 나누어 떨어지는 숫자가 됩니다.

 

그렇다면 1부터 A까지의 약수를 구할 때 N을 약수로 가지는 숫자는 A를 N으로 나눈 몫을 구하면 나올 것입니다.

 

1은 1, 2, 3, 4, 5 모두가 가지는 약수입니다.

1~5중 1을 약수로 가지는 개수 = 5 / 1 = 5개

 

2는 2와 4의 약수입니다.

1~5중 2을 약수로 가지는 개수 = 5 / 2 = 2개

 

 

결국 for문을 통해서 1~N까지를 돌면서 각 수를 약수로 가지는 숫자의 개수를 구할 수 있습니다.

 

 

 

발생한 문제 & 해결 방안

문제를 이해하는데 상당한 시간이 걸렸다.

문제 자체의 구문이 난해한 면이 있어서 힘들었던 것 같다.

 

이러한 약수를 더하는 문제를 처음봐서 어려웠다.