[백준/JAVA] 1016번: 제곱 ㄴㄴ 수

🔺 문제

1016번: 제곱 ㄴㄴ 수

 

🔺 코드

import java.util.*;
import java.io.*;
 
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[] check = new boolean[(int) (max - min + 1)];
        
        // 1) 제곱수 확인하기
        for(long i = 2 ; i * i <= max ; i++) {
            long pow = i* i;    // 제곱수
            long sIdx = min / pow;
            
            // 나머지가 있으면 1을 더해야 min보다 큰 제곱수에서 시작
            if(min % pow != 0) {
                sIdx++; 
            }
            
            // 몫을 1씩 증가시키면서 제곱수를 true로 변경 (j : 몫)
            for(long j = sIdx ; j * pow <= max ; j++) {
                check[(int) ((j * pow) - min)] = true;
            }
        }
            
        // 2) 제곱 ㄴㄴ수 갯수 세기    
        int cnt = 0;
        for(boolean b : check) {
            if(!b)
                cnt++;
        }
        
        System.out.println(cnt);
    }
}
 

✅ 해결 아이디어
✔ 에라토스테네스의 체 - 제곱수의 배수 형태로 탐색

 

💥 유의사항

 ⇨ 일반적 반복문으로 구하면 시간 초과 발생하므로 에라토스테네스의 체 사용

---

🔺 다른 풀이들

- 최고 친절한 설명...ㅠㅠ

(JAVA) 백준 1016번 : 제곱ㄴㄴ수

[백준 / JAVA] 백준 알고리즘 1016번 제곱 ㄴㄴ수 - 𝝅번째 알파카의 개발 낙서장

 

- 오... 짧아서 좋다

로그인

 

- 도중에  while문 쓰신게 신기해서..

로그인

---

💬 느낀 점

어렵구나.....

복습허자!!!

 

1회독	2회독	3회독	4회독	5회독
V	6/20

 

(+ 6/20 2회독)

사실 무슨 소린지 아직까지 확실하게 이해하진 못했으나...

얘는 복습할 때마다 거의 소수 문제랑 같이 복습해야겠다.

import java.util.*;
import java.io.*;
 
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[] check = new boolean[(int) (max - min + 1)];
        
        for(long i = 2 ; i * i <= max ; i++) {
            long pow = i * i; 
            long sIdx = (min % pow == 0) ? (min / pow) : (min / pow + 1);
            
            for(long j = sIdx ; j * pow <= max ; j++) {
                check[(int) ((j * pow) - min)] = true;
            }
        }
            
        int cnt = 0;
        for(boolean c : check) {
            if(!c)
                cnt++;
        }
        
        System.out.println(cnt);
    }
}