[백준] 1016 제곱 ㄴㄴ 수 java 풀이

1. 문제 설명 📌

(1) 링크🔗

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

(2) 해설🕵

제곱 ㄴㄴ 수 : 1보다 큰 제곱 수로 나누어 떨어지지 않는 수. 따라서 4이상 모든 제곱 수로 나누어 떨어지지 않아야 함

2. 생각의 흐름: 코드가 나오기까지 🗃️

(1) IDEA 도출💡

KEY WORD: 에라토스테네스의 체

a. 푸는 방향

삼국지에서 조조는 숲에서 게릴라 항전을 하는 황건적 잔당을 잡기 위해 숲에 직접 들어가기 보다 숲에 불을 질러서 살려고 나오는 잔당을 죽였다. 그처럼 모든 제곱 수로 나눠지지 않는 수(제곱 ㄴㄴ 수)를 일일히 구하는 것보다, 제곱 수로 나눠지는 수를 제거해서 결국엔 제곱 ㄴㄴ 수만 배열에 남기는 것이 간편할 것이다. 그렇다면 이제 구해야할 것은 제곱수와 그 배수 들인데, MAX 값 또한 제곱 수 자체 일 수 있으므로 우리가 구해야 하는 제곱 수의 범위는 $0 <= K^{2} <= MAX$ 가 될 것이다.

a. 제곱 수는 어디까지 구해야 할까?

제곱 수($K^{2}$)를 max의 최대값인 1조 100만까지 다 구한다면 필히 시간초과로 이어질 것이다. 하지만 $K^{2} <= MAX$ 를 제곱근으로 나누면, $K <= \sqrt{MAX}$ 가 된다. 이는 최대 $10^{6}$ 정도까지만 K를 구하면 되므로 시간 초과는 나지 않는다.

b. 어떻게 나타내지?

min의 최대값이 1조여서 대략 난감했다. 하지만 max를 보니 min과 최대 백만 밖에 차이가 나지 않는다. 따라서 범위 내의 수들을 배열로 나타낼 수 있었다. 즉 배열의 크기는 max - min이고 배열의 index는 min ~ max 사이의 숫자, value는 해당 수가 제곱 ㄴㄴ수이면 1, 아니면 0을 나타낸다. 당연히 index를 min부터 시작할 수 없으므로, 실제 나타내려는 수가 K라면index = K - min으로 초점을 조정한다.

이제 우리는 min에서 max 까지의 수들 중에, 제곱 수의 배수들을 찾고 Value = 0으로 만들면 된다. 하지만 여기서 걸림돌이 생긴다. 바로 'K라는 임의의 제곱 수의 배수 중 min보다 큰 최초의 값을 어떻게 찾을까?' 이다. 만약 제곱수의 배수를 1부터 시작하여 완전탐색으로 찾는다면 분명히 시간초과가 날 것이다. 예를 들어 min 이 1조라고 했을 때, 4의 배수 중 1조를 넘는 최초의 값을 찾기 위해 처음부터 하나씩 곱하는 것을 생각해보아라.

c. min보다 크거나 같으면서 제일 가까운 제곱수의 배수 찾기

답은 의외로 쉽다. 현재 우리가 계산할 제곱 수를 $K^{2}$라고 할 때, $\frac{min}{K^{2}}$의 몫을 찾는다. 만약 $\frac{min}{K^{2}}$의 나머지가 0이라면, min이 곧 시작점이 될 것이다. 만약 나누어 떨어지지 않는다면, $K^{2}$의 min보다 큰 시작점은 $K^{2} * (몫 + 1)$이 될 것이다.
왜냐하면 $min = K^{2} * 몫 + 나머지$라면 $min > K^{2} * 몫$ 이라는 소리이다. 이때, $K^{2} * 몫$은 min보다 작으면서 제일 가까운 수가 된다. 따라서 다음 배수인 $K^{2} * (몫 + 1)$은 min보다 크면서 제일 가까운 수가 된다.
이제 이 값을 시작점으로 max까지 $K^{2}$의 배수를 찾으면 된다.

d. 배열 내에서 위치 찾기

b번까지 구한 배수들은 모두 min ~ max 사이의 값이다. 따라서 우리가 구한 배수에 -min 을 해주면 그것이 배열의 index가 된다. 해당 index의 value를 0으로 바꿔주면 된다.

(2) SUDO CODE 📜

• 1️⃣ 2에서 $\sqrt{MAX}$ 까지의 수를 차례대로 조회 한다.
• 2️⃣ 1번에서 찾은 수를 제곱해서 제곱 수($K^{2}$) 형태로 만든다.
• 3️⃣ 위에서 했던 설명 처럼 min보다 크거나 같으면서 min에 제일 가까운 $K^{2}$의 배수를 찾는다.
• 4️⃣ 3번에 찾은 값을 시작점으로 배수의 계수를 높여가며 배열에서 제외 한다.
• 5️⃣ 남은 값들의 개수를 센다.

(3) 시간복잡도 분석 🕓

• $K^{2}$ 구하기: $O(10^{6})$
• 배수의 시작점 찾기: $O(1)$
• 시작점 부터 배수 지우기: 제일 많은 반복문을 도는 것은 4의 배수를 찾을 때 일 것이다. 그것의 반복 횟수를 보면$O100,000/4$ 이다. 제곱수($K^{2}$)가 커질수록 이 연산횟수는 줄 것이다. $(100,000/4 + 100,000/9 ...)$

결론: $O(10^{6} * 1 * ???)$

여튼 1초에 2억번보단 작은 듯 ㅎ

3. 구현 코드 🔎

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
    static long min, max;
    static int [] nums;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st= new StringTokenizer(br.readLine());
        min = Long.parseLong(st.nextToken());
        max = Long.parseLong(st.nextToken());
        nums = new int [(int)(max-min+1)];
        Arrays.fill(nums, 1);
        square_sieve();
        System.out.println(Arrays.stream(nums).sum());
    }

    public static void square_sieve () {
        for (long i = 2; i <= Math.sqrt(max); i++) {
            long square = i*i;
            long delete_start = 0;
            if(min%square != 0) delete_start = (min/square) + 1;
            else delete_start = min/square;

            for (long j = delete_start; j*square <= max; j++) {
                nums[(int)(j*square - min)] = 0;
            }
        }
    }
}

4. 배운 것들 🎯

다른 사람의 풀이를 보고 배운 기술

System.out.println(Arrays.stream(nums).sum());

배열을 boolean이 아니라 0, 1을 가지는 값으로 하고, 유효한 위치의 value = 1로 놔둔다. 이후 stream을 사용해 다 더해버리면, 답을 빠르게 구할 수 있다.