[백준 - 1016번] 제곱 ㄴㄴ수 - Java //Wello Horld//

이번에는 BOJ의 1016번 문제 "제곱 ㄴㄴ수"를 풀어보도록 하자

문제는 간단하다. 입력으로 minimum인 min 과 maximum인 max가 주어진다. 그리고 min과 max를 포함한 사이에 제곱 ㄴㄴ수 가 얼마나 있는지 출력하는 문제이다. 일단, max >= min + 1,000,000(백만) 이기 때문에, 이 사이에 수들에 대해서만 반복문으로 구해주면 된다. 여기에서, 유의해야 될 점은 min이 1 보다 크거나 같고, 1,000,000,000,000(1조) 보다 작거나 같은 자연수 라는 점이고, 이 부분을 유의해서 min과 max를 long 자료형으로 받아왔다.

성공한 코드는 아래와 같다.

import java.io.*;
import java.util.*;

public class sample {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        long min = Long.parseLong(st.nextToken());
        long max = Long.parseLong(st.nextToken());
        //min 과 max 를 포함한 사이부분
        boolean[] cache = new boolean[(int)(max - min + 1)];
        //2의 제곱수인 4부터 max보다 작은 수 까지 제곱수를 반복문을 통해 구해줌
        for(long i = 2; i * i <= max; i++){
            long power = i * i;
            //min보다 큰 위에서 구한 제곱수의 시작값(몫)을 start로 지정
            long start = min % power == 0 ? min / power : (min / power) + 1;
            for(long j = start; power * j <= max; j++){
                cache[(int)((j * power) - min)] = true;
            }
        }
        int count = 0;
        //min 과 max 를 포함한 사이부분에 제곱ㄴㄴ수가 얼마나 있는지 구해줌
        for(int i = 0; i <= max - min; i++){
            if(!cache[i]){
                count++;
            }
        }
        bw.write(count + "\n");

        bw.flush();
        br.close();
        bw.close();
    }
}