[백준] 1016번 : 제곱ㄴㄴ수 Gold1(골드1) - JAVA[자바]

[Gold I] 제곱 ㄴㄴ 수 - 1016

문제 링크

성능 요약

메모리: 12708 KB, 시간: 124 ms

분류

수학, 정수론, 소수 판정, 에라토스테네스의 체

제출 일자

2023년 12월 19일 18:14:50

문제 설명

어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

입력

첫째 줄에 두 정수 min과 max가 주어진다.

출력

첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다.

 

풀이 방법

1. min과 max의 최대 범위가 크기 때문에 Long 타입을 사용해야함

2. min과 max의 차이는 최대 1,000,000밖에안나니까 배열로 처리가 가능하다.

3. 2부터 시작하여 max의 밑까지 제곱수를 전부 처리해주면된다.
4. 에라토스테네스의 체 알고리즘을 활용하면 좋음

5. 시작값이 min보다 작다면 비효율적인 처리를 함으로 시작값을 잘 처리해주어야 함

  ex) i * i = 4, min = 10 이라면 start는 i * i * 3 = 12부터 제거해주면 된다.

6. 배열에 들어갈 실제 값 중 제곱수로 나누어진다면 전부 true처리

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 최소값과 최대값을 입력받아 범위만큼의 배열 생성
        long min = Long.parseLong(st.nextToken());
        long max = Long.parseLong(st.nextToken());
        boolean[] visit = new boolean[(int) (max - min + 1)];

        // 2부터 2의 제곱이 max보다 작거나 같을 때 까지 진행해줌(제곱수가 max보다 크다면 처리 곤란)
        for(long i = 2; i * i <= max; i++){
            long pow = i * i;

            // 시작 지점은 min보다 크거나 같아야하기 때문에 나누어 떨어진다면 몫부터 아니라면 몫+1부터 시작
            long start = min % pow == 0 ? (min / pow) : (min / pow) + 1;

            // 제곱수의 배수들을 전부 제거해줌
            for (long j = start; j * pow<= max; j++) {
                // j는 min <= j <= max 실제 범위를 다루기 때문에 min을 빼주어 배열에 사용할 수 있도록 함
                int idx = (int) (j * pow - min);
                if(!visit[idx]){
                    visit[idx] = true;
                }
            }
        }

        int count = 0;
        for (boolean v : visit) {
            if(!v) count++;
        }
        System.out.println(count);
    }
}