[java] 문제040 (백준 1016)

문제

제곱ㄴㄴ수

 

교재 풀이

import java.util.*;
public class P1016_제곱이아닌수 {
  public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
    long Min = sc.nextLong();
    long Max = sc.nextLong();
    boolean[] Check = new boolean[(int) (Max - Min + 1)]; // 최대 최소 차이만큼 배열 선언
    // 2의 제곱수인 4부터 max보다 작거나 같은 까지 반복
    for (long i = 2; i * i <= Max; i++) {
      long pow = i * i; // 제곱수
      long start_index = Min / pow;
      ;
      if (Min % pow != 0)
        start_index++; // 나머지가 있으면 1을 더해주어야 Min보다 큰 제곱수 부터 시작됨
      for (long j = start_index; pow * j <= Max; j++) { // 제곱수를 true로 변경
        Check[(int) ((j * pow) - Min)] = true;
      }
    }
    int count = 0;
    for (int i = 0; i <= Max - Min; i++) {
      if (!Check[i]) {
        count++;
      }
    }
    System.out.println(count);
  }
}

 

내 풀이) 24.6.20에 풀고 틀림

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

public class Main
{
	public static void main(String[] args) throws IOException{
        Scanner sc=new Scanner(System.in);
        long min=sc.nextLong();
        long max=sc.nextLong();
        
        long[] a=new long[(int)(max-min+1)];
            //min 3 max 10이면 크기는 8, 0~7 인덱스 
            // 인덱스 0엔 3이, 7엔 10이 매핑됨 
            // 아님 쉽게 min+max=13이고, 그럼 0~12 인덱스고 
            // min, max가 더해주면 메모리 초과 뜰 것 같은데 그럼 기존대로 하지 뭐 
        for(int i=0;i<a.length;i++){
            a[i]=i+min;
        }
        
        boolean[] check=new boolean[a.length];
        for(long i=2;i<=Math.sqrt(max);i++){
            long pow=i*i;
            long sIndex=min/pow;
            if(min%pow!=0)
                sIndex++;
            
            for(long j=sIndex*pow;j<=max;j*=i){
                check[(int)(j-min)]=true;
            }
        }
        
        long cnt=0;
        for (int i=0;i<a.length;i++){
            if(check[i]==false)
                cnt++;
        }
        System.out.println(cnt);
        
	}

}

        
// 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수
//     제곱수는 정수의 제곱 => 즉 2의 제곱, 3의 제곱, 4의 제곱으로 나눠 떨어지지 않을 때라 
// min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력
//     1 ≤ min ≤ 1,000,000,000,000 (1조)
//     min ≤ max ≤ min + 1,000,000
//     => 어차피 min과 max 사이 제곱ㄴㄴ수를 구하는 거니까,
//     백만을 찾는다고 치면 됨 
//     => 일단 배열은 long으로 해야 겠네 

// 접근법
//     일단은 배열 a을 하나 선언해주는데
//         일단 long으로 해주고 
//         크기는 max-min+1로 해줘서, min부터 max 사이의 수를 대상으로 함을 의미 
//     제곱ㄴㄴ수는 
//         제곱수로 안 나눠지는 것 => 즉 에라토스테네스의 체를 응용하면 
//         제곱수의 배수의 경우, 제곱수로 나눠지니까 제외하는 거지. 
//         마치 소수의 배수는 다 소수가 아니라고 제외하는 것처럼 
//             이 때 소수의 경운 아닌 건 0으로 업데이트 했지만 
//             이번엔 check 배열을 만들어서
//             제곱수의 배수인 경우 true로 해주기로 함 
//     그 다음 출력은 
//         당근 check 배열을 가지고 하는데 
//         check배열 중 false인 원소 만날 때마다 
//         cnt++해준 후 최종 cnt를 출력하면 됨 
// 슈도코드 
//     min, max가 주어지니 입력
//         long으로 입력 
        
//     long 배열 a를 만들어줌 
//         크기는 max-min+1로 해주고 
//         for i=min i<=max i++ 
//             a[i]=i 
    
//     boolean check 배열 만들어줌
//         제곱수의 배수일 때 true로 바꿔줄 거임 
//         크기는 똑같이 a.length로 해주면 되지 않을까
//     for i=2 i<= sqrt(max) i++ 
//         pow: i*i 
//         sIndex: min/pow
//         if sIndex %!=0 
//             sIndex++
        
//         for j=sIndex*pow; j<=max; j*=i 
//             check[j-min]=true 
    
//     long cnt 
//     for a.length만큼 반복하며 
//         check[i]==false 
//             cnt++ 
//     print cnt

 

설명

24.6.20 내 풀이 => 그냥 나중에 다시 한 번 풀면 맞을 것 같음. 교재 풀이 내용을 어느 정도 이해했지만 완전하지 않아서 지금은 틀렸지만, 나중에 수준 높아지고 이해 올라가면 그대로 풀 듯