[백준] 17427번 - 약수의 합 2 [Java]

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

 

[백준] 17427번 - 약수의 합 2 [Java]

[백준] 17427번 - 약수의 합 2 [Java]

---

1.  아이디어

 

문제의 설명대로 1부터 N까지 각 자연수의 약수의 합을 구하고 이를 다시 더하는 방식으로는 시간안에 해결할 수 없다. 반대로 1부터 N까지의 수가 g(N)에 몇 번 등장할지를 찾으면 간단하게 해결할 수 있는데 1은 1부터 N까지 1의 배수의 수만큼 등장하고 2는 2의 배수의 수만큼 등장하고 3은 3의 배수의 수만큼 등장한다. 이를 활용하면 간단하게 해결할 수 있다.

---

2. 문제풀이

 

배수는 나눗셈 연산으로 구할 수 있고 등장한 수의 합을 구하기 위해 해당 수를 곱하는 과정을 반복하면 간단하게 해결할 수 있다. g(N)을 구하는 과정에서 int형 오버플로우가 발생할 수 있음에 주의해야한다.

---

3. 코드

 

import java.io.*;

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

        long N = Long.parseLong(br.readLine());

        long sum = 0;

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

        System.out.println(sum);
    }
}

---

4. 후기