- [백준 / JAVA] 백준 알고리즘 1021번 회전하는 큐
- [백준 / JAVA] 백준 알고리즘 1020번 디지털 카운터
- [백준 / JAVA] 백준 알고리즘 1019번 책 페이지
- [백준 / JAVA] 백준 알고리즘 1018번 체스판 다시 칠하기
- [백준 / JAVA] 백준 알고리즘 1017번 소수 쌍
👀 [백준 / JAVA] 백준 알고리즘 1016번 제곱 ㄴㄴ수
- [백준 / JAVA] 백준 알고리즘 1015번 수열 정렬
- [백준 / JAVA] 백준 알고리즘 1014번 컨닝
- [백준 / JAVA] 백준 알고리즘 1013번 Contact
- [백준 / JAVA] 백준 알고리즘 1012번 유기농 배추
- [백준 / JAVA] 백준 알고리즘 1011번 Fly me to the Alpha Centauri
- [백준 / JAVA] 백준 알고리즘 1010번 다리 놓기
- [백준 / JAVA] 백준 알고리즘 1009번 분산처리
- [백준 / JAVA] 백준 알고리즘 1008번 A / B
- [백준 / JAVA] 백준 알고리즘 1007번 벡터
- [백준 / JAVA] 백준 알고리즘 1006번 습격자 초라기
- [백준 / JAVA] 백준 알고리즘 1005번 ACM Craft
- [백준 / JAVA] 백준 알고리즘 1004번 어린 왕자
- [백준 / JAVA] 백준 알고리즘 1003번 피보나치 함수
- [백준 / JAVA] 백준 알고리즘 1002번 터렛
- [백준 / JAVA] 백준 알고리즘 1001번 A - B
- [백준 / JAVA] 백준 알고리즘 1000번 A + B
- 백준 알고리즘 시작하기
제곱 ㄴㄴ수 🔗
조건 🔗
시간제한 | 메모리 제한 |
---|---|
2초 | 512MB |
문제 🔗
어떤 수 가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다.
입력 🔗
첫째 줄에 두 정수 min과 max가 주어진다.
출력 🔗
첫째 줄에 [min,max]구간에 제곱ㄴㄴ수가 몇 개인지 출력한다.
제한 🔗
케이스 🔗
예제 1 🔗
- 입력
TC
0 | 1 10 |
- 출력
TC
0 | 7 |
풀이 🔗
주어진 구간에서 제곱수(4, 9, 16 등)으로 나누어지지 않는 수의 갯수를 구하면 되는 문제.
개념은 생각보다 간단하다. 에라토스 테네스의 체에 대해 알고있다면 생각보다 쉽게 접근할 수 있기도 하고. 의외로 문제는 다른 쪽에 있다.
- min, max의 최대값이 1조 단위다.
- 구간이 반드시 1부터 시작하지 않는다.
- 배열의 인덱스는 반드시
int
데이터만 가능하다.
보편적인 정수 데이터인 int
의 최대값이 약 21억인걸 감안하면 턱없이 큰 수. 때문에 long
데이터의 사용이 강제된다. 반면 배열의 인덱스는 int
데이터만 사용 가능하므로, int
와 long
의 적절한 데이터 선언 및 변환이 필요하다.
최소값 min과 최대값 max는 그 수가 매우 클 수는 있어도, 그 차이는 백만 이하로만 나오므로 배열로 다루는데 무리가 없다.
만약, min = 1,000,000,000,000(1조)이고, max = 1,000,000,500,000(1조 50만)일 경우, 실제로 비교해야할 구간은 약 50만개밖에 되지 않는다. 이 구간을 배열 로 표시하면 가 된다. 즉, 으로 다뤄야한다.
제곱수의 배수를 제외해야한다는 점에서 소수의 배수를 제외하여 소수를 판별하는 에라토스 테네스의 체의 개념와 매우 흡사하다. 즉, 에라토스 테네스의 체 알고리즘에서 소수가 아닌 제곱수의 배수를 판별하게끔 살짝 변형시켜주면 된다.
전체 소스 🔗
JAVA
0 | import java.io.BufferedReader; |
1 | import java.io.BufferedWriter; |
2 | import java.io.IOException; |
3 | import java.io.InputStreamReader; |
4 | import java.io.OutputStreamWriter; |
5 | import java.util.Arrays; |
6 | |
7 | /** |
8 | * 백준 전체 1016 문제 알고리즘 클래스 |
9 | * |
10 | * @author RWB |
11 | * @see <a href="https://blog.itcode.dev/posts/2021/06/23/a1016">1016 풀이</a> |
12 | * @since 2021.06.23 Fri 00:22:31 |
13 | */ |
14 | public class Main |
15 | { |
16 | // 최소값 |
17 | private static long min; |
18 | |
19 | // 최대값 |
20 | private static long max; |
21 | |
22 | /** |
23 | * 메인 함수 |
24 | * |
25 | * @param args: [String[]] 매개변수 |
26 | * |
27 | * @throws IOException 데이터 입출력 예외 |
28 | */ |
29 | public static void main(String[] args) throws IOException |
30 | { |
31 | BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); |
32 | BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out)); |
33 | |
34 | long[] temp = Arrays.stream(reader.readLine().split(" ")).mapToLong(Long::parseLong).toArray(); |
35 | |
36 | min = temp[0]; |
37 | max = temp[1]; |
38 | |
39 | writer.write(Integer.toString(solve())); |
40 | writer.newLine(); |
41 | |
42 | writer.close(); |
43 | reader.close(); |
44 | } |
45 | |
46 | /** |
47 | * 알고리즘 결과 반환 함수 |
48 | * |
49 | * @return [int] 제곱수로 나누어 떨어지지 않는 수의 갯수 |
50 | */ |
51 | private static int solve() |
52 | { |
53 | int size = 0; |
54 | |
55 | boolean[] isNotPow = eratosthenes(); |
56 | |
57 | for (boolean item : isNotPow) |
58 | { |
59 | // 제곱수로 나누어 떨어지지 않는 수일 경우 |
60 | if (!item) |
61 | { |
62 | size++; |
63 | } |
64 | } |
65 | |
66 | return size; |
67 | } |
68 | |
69 | /** |
70 | * 에라토스 테네스의 체 배열 반환 함수 |
71 | * true: 제곱ㄴㄴ수가 아닌 수 |
72 | * false: 제곱ㄴㄴ수 |
73 | * |
74 | * @return [boolean[]] 에라토스 테네스의 체 배열 |
75 | */ |
76 | private static boolean[] eratosthenes() |
77 | { |
78 | int length = (int) (max - min + 1); |
79 | |
80 | boolean[] isNotPow = new boolean[length]; |
81 | |
82 | for (long i = 2; i * i <= max; i++) |
83 | { |
84 | long pow = i * i; |
85 | |
86 | long start = min % pow == 0 ? min / pow : (min / pow) + 1; |
87 | |
88 | for (long j = start; j * pow <= max; j++) |
89 | { |
90 | // 제곱수의 배수로 나누어 떨어지므로 제곱ㄴㄴ수가 아님 |
91 | isNotPow[(int) (j * pow - min)] = true; |
92 | } |
93 | } |
94 | |
95 | return isNotPow; |
96 | } |
97 | } |
solve()
메소드는 단순히 갯수를 파악하는 로직이므로 그 의도만 알면 된다. 가장 핵심인 부분은 에라토스 테네스의 체를 변형한 아래 코드다.
JAVA
0 | /** |
1 | * 에라토스 테네스의 체 배열 반환 함수 |
2 | * |
3 | * true: 제곱ㄴㄴ수가 아닌 수 |
4 | * false: 제곱ㄴㄴ수 |
5 | * |
6 | * @return [boolean[]] 에라토스 테네스의 체 배열 |
7 | */ |
8 | private static boolean[] eratosthenes() |
9 | { |
10 | int length = (int) (max - min + 1); |
11 | |
12 | boolean[] isNotPow = new boolean[length]; |
13 | |
14 | for (long i = 2; i * i <= max; i++) |
15 | { |
16 | long pow = i * i; |
17 | |
18 | long start = min % pow == 0 ? min / pow : (min / pow) + 1; |
19 | |
20 | for (long j = start; j * pow <= max; j++) |
21 | { |
22 | // 제곱수의 배수로 나누어 떨어지므로 제곱ㄴㄴ수가 아님 |
23 | isNotPow[(int) (j * pow - min)] = true; |
24 | } |
25 | } |
26 | |
27 | return isNotPow; |
28 | } |
총 2개의 반복문이 돌아간다. 인덱스는 각각 , 다.
- : 제곱수의 제곱근
- : 제곱수의 배수를 구하기 위한 인덱스
1보다 큰 제곱수는 4이므로, 인덱스 의 시작값은 2이며, 제곱수인 의 크기가 max 이하일때 까지 반복한다. 만약, 구간이 10부터 30까지라면, 는 2(4)부터 5(25)까지 증가할 것이다.
인덱스 는 약간 복잡한데, 이는 구간의 존재 때문이다. 기본적으로 에라토스 테네스의 체는 1부터 시작하므로 상관없지만, 해당 문제는 시작값이 1이 아닐 경우가 존재한다.
예를 들어, 이고 구간이 10 ~ 20까지라고 가정하자. 이므로 제곱수 4의 배수를 제거해야한다. 만약 평상시처럼 곱셈의 인덱스를 1부터 시작해서 , , 와 같이 시작한다면 문제가 생긴다. 구간은 10부터인데 비해, 10 이하인 4, 8을 제거하게되니 이를 걸러내야한다. 만약 구간이 1000부터 시작이라면 250개의 쓸모없는 연산이 발생한다. 구간이 최대 1조부터 시작할 수 있음을 생각한다면 구간의 시작에 따라 곱셈 인덱스 를 적절히 계산해야한다.
일 경우, 이다. 구간의 시작이 10일 경우, 10 이하인 수 , 는 건너뛰므로 곱셈 인덱스 는 3부터 시작해야한다.
즉, 곱셈 인덱스 의 시작값의 일반식은 위와 같다.
이므로, 해당값을 모두 제외하면 된다. 단, 는 실제 값이므로, 배열의 인덱스는 이다.
배열에 true
를 할당하는 이유는 boolean[]
의 초기값이 false
이기 때문. Arrays.fill()
메소드를 활용하여 true
로 초기화할 수도 있으나, 의미론적으론 좋지만 불필요한 연산이므로 false
를 제곱ㄴㄴ수로, true
를 제곱ㄴㄴ수가 아닌 수로 지칭한다. 배열 이름이 isNotPow
인 이유도 이때문.
이후 isNotPow
배열을 순회하며, 값이 false
인 수만 카운팅하면 된다.
분류 🔗
- 수학
- 정수론
- 소수 판정
- 에라토스 테네스의 체
📆 작성일
2021-06-23 Wed 00:22:31
📚 카테고리
🏷️ 태그