[백준] 1016 제곱 ㄴㄴ 수

2023. 5. 2. 23:12💻코딩/💡Baekjoon

728x90
반응형

[문제 링크]

 

1016번: 제곱 ㄴㄴ 수

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

www.acmicpc.net

 

import java.util.*;

public class Main {
	static int count = 0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		long min = sc.nextLong();
		long max = sc.nextLong();

		boolean[] check = new boolean[1000001];
		long end = (long)Math.sqrt(max);

        //에라토스테네스의 체 원리
		for(long i = 2; i < end+1; i++) {
			long temp = i*i;
			long start = 0;
			if(min % temp == 0) {
				start = min / temp;
			}else {
				start = (min / temp) + 1;
			}
			for(long j = start; j*temp < max+1; j++) {
				check[(int)((j*temp)-min)] = true;
			}
		}

		for(int i = 0; i < (max-min+1); i++) {
			if(check[i]==false) {
				count++;
			}
		}
		System.out.println(count);
	}
}

이번 문제는 겉보기에 쉬워보였고, for문과 if문을 통해 쉽게 구현했지만 문제가 있었다.

바로 시간초과이다..❕이는 for문을 여러번 돌고  min, max의 숫자 자체가 커서 생기는 오류였다.

 

이를 해결하기 위해서는 '에라토스테네스의 체 원리' 를 사용해야 한다.

에라토스테네스의 체 원리란, 소수를 빠르게 찾는 방법이다. 
2부터 시작하게 될 경우, 차례대로 소수의 배수를 제거한다. (이때, 본인은 제거하지 않는다.)
이를 반복하면 최종적으로 모든 소수가 남는다.

 

에라토스테네스 체 원리에 대한 쉬운 이해와 설명은 아래의 블로그를 참고하길 바란다.

 

[JAVA] 소수 찾기 - 에라토스테네스의 체

문제에 대해서는 여기를 클릭하여 가면 된다. 이번에 프로그래머스를 풀면서 에라토스테네스의 체를 사용하여 이 알고리즘을 설명하는 김에 문제풀이도 같이하려 가지고 왔다. 일단 에라토스

krapoi.tistory.com

 

이 문제에서는 boolean 타입의 check 배열을 만들어 소수를 체크할 수 있도록 하였고,

입력값을 min = 1, max = 10으로 주었을 때, 가장 작은 제곱수인 4를 시작으로

min을 4로 나누었을 때, 나누어 떨어지면 start의 값을 몫으로, 그렇지 않으면 몫 + 1값을 가져가도록 하고, 

지금은 min의 값이 1이므로 start = 1이된다.

1*4 = 4이고, 4는 1~10 사이의 값이므로 check 배열의 해당 인덱스 값을 ture로 지정한다.

그 이후 제곱수의 수를 늘려가며 반복하고 최종적으로 check 배열의 값이 false인 제곱 ㄴㄴ수의 수를 출력하면 된다.

728x90
반응형

'💻코딩 > 💡Baekjoon' 카테고리의 다른 글

[백준] 1021 회전하는 큐  (2) 2023.12.13
[백준] 1015 수열 정렬  (0) 2023.05.18
[백준] 1014 컨닝  (0) 2023.02.04
[백준] 1013 Contact  (1) 2023.01.16
[백준] 1012 유기농 배추  (2) 2023.01.13