[백준 Java] 2247번 실질적 약수(정수론)

💡문제

[Gold V] 실질적 약수 - 2247

문제 링크

성능 요약

메모리: 11588 KB, 시간: 732 ms

---

깨진 부분은 여기에서 확인

🤔접근법

범위 체크 및 시간복잡도 예상

• 1 ≤ n ≤ 200,000,000 .. 2억
• 시간 제한이 2초라 $O(N)$ 도 가능할 거 같다.

풀이법

❌ 첫번째 접근 방법 . 에라토스테네스의 체

1. 소수 판별 (에라토스테네스의 체) $O(log(logN))$
2. 소수가 아닌 N에 대해 순회 $O(N)$ → (여기가 이미 188,921,062)
3. 실질적 약수 구하기 SCD(N) $O(\sqrt N)$

➡️ 해당 풀이법의 시간 복잡도 : $O(N\sqrt N)$이다

⭕ 두번째 접근 방법 . N까지 x의 배수의 개수

1. 1 ~ N까지 순회 $O(N)$
2. N 이하의 수에서 어떤 수 i를 약수로 가지는 수의 개수 $O(1)$
   • N / i

그럼 2번 과정에 대해서 자세히 알아보자

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
2를 약수로 가지는 수		제외		O		O		O		O		O		O		O		O		O
3를 약수로 가지는 수			제외			O			O			O			O			O
4를 약수로 가지는 수				제외				O				O				O				O
5를 약수로 가지는 수					제외					O					O					O
- 2를 약수로 가지는 수의 개수는 ( 20 / 2 ) = 10 -1 이때, 자기자신을 약수로 가지고 있는애는 실질적인 약수가 아니기 때문에 제외한다. ( -1의 이유)
- 3를 약수로 가지는 수의 개수는 20 / 3 = 6 -1
- 4을 약수로 가지는 수의 개수는 20 / 4= 5 -1
- 5을 약수로 가지는 수의 개수 20 / 5 = 4 -1

이때 유의 사항은 1과 N을 포함하지 않고 반복해야한다.

이 과정을 2 ~ 19 까지 모두 진행하게 되면

i * i를 약수로 가지는 수의 개수 들의 합이

(2 * 9) + (3 * 5) +( 4 * 4) + (5 * 4) + … = SCDN(20) 이 된다.

➡️ 해당 풀이법의 시간 복잡도 : $O(N)$이다

---

🤯FAIL

첫 번째 접근 ▶️ 시간 초과 - 잘못 계산한 이유

2번 순회 하는 과정을 빼먹었다. (위에 작성한 것은 수정하여서 옳은 시간복잡도)

1 ~ N까지 순회하면서 N의 약수를 구하는 로직인데 소수이면 넘어가고 소수가 아닌 경우에만 약수를 구한다.

나는 여기서 소수인 경우만 로직을 수행하니까 순회하는 시간복잡도인 O(N)을 무시해도 되겠다 생각했는데

실제로 계산해보니 200,000,000 까지 소수가 아닌 수는 188,921,062개나 있었다.

그러면 10,000 * 100,000,000 만 해도 이미 .. 시간 초과이다 .

😎SUCCESS

두 번째 접근 ▶️ 성공

---

👩‍💻 코드

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

public class Main_2247 {
    static int n;

    static long sum;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        sum = 0;
        for (int i = 2; i < n; i++) {
            sum += ((n/i)-1) * i;
        }

        System.out.println(sum%1000000);


    }
}