며칠간 나를 괴롭힌 문제로, 사람에 따라 어떤 문제보다도 어렵게 느껴질 수 있다.
음.. 문제 자체가 어려운 건 아니지만 비슷한 유형의 문제가 나왔을 때 풀 수 있을 거라는 자신이 없다.
결국 반 쯤 혼자 풀었는데도 기쁘지 않고 짜증나는 문제.. ㅎ
우선 문제를 읽고 조건을 정리해보자.
문제가 짧고 심플하다는 것은 더 생각해야할 조건이 있다는 뜻이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
|
public class Main {
// 소수의 N제곱 = 거의 소수
// A보다 크거나 같고, B보다 작거나 같은 모든 거의 소수를 구하라.
// A와 B는 10^14보다 작거나 같다.
// 2^31-1가 몇인지는 정확하게 모르지만, 10^14보다 작다는 것은 확실하다.
// long으로 입력받아야 함.
// 용량이 256MB -> 에라토스테네스의 체 사용 가능 public static void main(String[] args) throws Exception {
}
}
|
cs |
1. 어떤 소수의 N제곱 = 거의 소수이다.
단, 소수 자체가 N제곱은 아님에 유의해야 한다.
2. A보다 크거나 같고, B보다 작거나 같은 모든 거의 소수를 받아야하며, A와 B는 10^14보다 작거나 같다.
내가 정수형의 최대 값인 2^31-1이 몇인지는 정확히 외우지 않고 있지만, 10^14보다 작다는 사실은 확실히 알고 있다.
그냥 아는 건 아니고 직접 써봤다. 100000000000000인데.. 딱 보면 알겠죠 ㅎㅎ
아무튼 너무 쉬워보이는 문제다.
그냥 long으로 입력 받고 에라토스테네스의 체로 소수 배열 만든 뒤에 각 소수 제곱하며 구하면 끝 아닌가?
날로 먹는 문제로구만.
수도 코드를 작성해보자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
public class Main {
// 소수의 N제곱 = 거의 소수
// A보다 크거나 같고, B보다 작거나 같은 모든 거의 소수를 구하라.
// A와 B는 10^14보다 작거나 같다.
// 2^31-1가 몇인지는 정확하게 모르지만, 10^14보다 작다는 것은 확실하다.
// long으로 입력받아야 함.
public static void main(String[] args) throws Exception {
// A, B 입력 받기
// A 선언 및 초기화
// B 선언 및 초기화
// 소수여부 저장할 배열 생성 (취향에 따라 정수형 혹은 boolean으로)
// 에라토스테네스의 체(배열, 최대값)
// 거의 소수 찾기(배열, 최소값, 최대값)
// 결과 출력
}
// 에라토스테네스의 체(불리언 배열, 최대값)
// 너무 쉬워서 이건 생략한다.
// 거의 소수 찾기(배열, 최소값, 최대값)
//
// 반복문 ( i<배열) {
// if (arr[i] == 소수) ?? {
// while( arr[i] <= 최대값 )
// iff (arr[i] >= 최소값)
// count ++
// }
// }
//
// 결과 반환
}
|
cs |
문제가 없어보인다.
그러면 오늘은 이대로 바로 작성하겠다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
public class Main {
// 소수의 N제곱 = 거의 소수
// A보다 크거나 같고, B보다 작거나 같은 모든 거의 소수를 구하라.
// A와 B는 10^14보다 작거나 같다.
// 2^31-1가 몇인지는 정확하게 모르지만, 10^14보다 작다는 것은 확실하다.
// long으로 입력받아야 함.
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// A, B 입력 받기
String[] arr = br.readLine().split(" ");
// A 선언 및 초기화
long A = Long.parseLong(arr[0]);
// B 선언 및 초기화
long B = Long.parseLong(arr[1]);
// 소수여부 저장할 배열 생성 (취향에 따라 정수형 혹은 boolean으로)
boolean[] isNotPrimeNum = new boolean[10000000 + 1];
// 에라토스테네스의 체(배열, 최대값)
getPrimeNumArr(isNotPrimeNum, B);
// 거의 소수 찾기(배열, 최소값, 최대값)
int result = getNearlyPrimeNumCount(isNotPrimeNum, A, B);
// 결과 출력
System.out.println(result);
}
// 에라토스테네스의 체(불리언 배열, 최대값)
public static void getPrimeNumArr(boolean[] arr, long max) {
arr[0] = arr[1] = true;
for (int i = 2; i*i<=max; i++) {
if (!arr[i]) {
for (int j=i+i; j<=max; j+=i) {
arr[j] = true;
}
}
}
}
// 너무 쉬워서 이건 생략한다.
// 거의 소수 찾기(배열, 최소값, 최대값)
public static int getNearlyPrimeNumCount(boolean[] isNotPrimeNum, long min, long max) {
int count = 0;
// 반복문 ( i<배열) {
for (int i=2; i< isNotPrimeNum.length; i++) {
// if (arr[i] == 소수) ?? {
if (!isNotPrimeNum[i]) {
long current = (long)i*i;
// while( arr[i] <= 최대값 )
while (current <= max) {
// iff (arr[i] >= 최소값)
if (current >= min) {
current = current * i;
count++;
// count ++
// }
// }
//
// 결과 반환
} else break;
}
}
}
return count;
}
}
|
cs |
얼핏 봤을 때는 괜찮아보이는 코드다.
일단 잘못된 부분이 세가지 있다.
1. A와 B의 최대값은 10^14다.
이 사이에 제일 큰 소수가 몇인지는 모르지만, 확실한 건 10^28이라는 단위의 숫자는 Long으로 받을 수 없다는 것이다.
그래서 우리는 거의 소수를 구하는 공식인 소수*소수에 순진하게 당하면 안된다.
그렇지만 우리는 지금까지 이런 문제에 단련됐기 때문에, "최대값을 넘는다?" => "이항정리하면 되겠네!"라는 생각을 할 수 있다.
현재의 조건이 current * i <= max일 때 반복문이 돌아간다는 것인데, 이걸 이항정리해보면 이런 형태가 된다.
current <= max / i 벌써 아주 좋아보인다.
2. 또한 에라토스테네스의 체도 이상하게 작성했는데, 최대값이 10^14라면 거의 소수는 소수의 제곱이기 때문에 10^14의 제곱근인 10^7까지만 구하면 된다.
3. while문도 정신을 놨는지 이상한 곳에 break을 달아놨다. 상식적으로 봐도 문제가 있다는 걸 알수 있으니 설명은 생략.
이제 정말 완벽해보인다.
근데 틀린다.
이유가 뭘까?
나는 이 하찮은 이유로 무려 2일을 낭비했다.
반례는 5 5
직접 풀어보자.
너무 오래 고민하지 말고 모르겠으면 그냥 답 보자.. 현타만 온다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] arr = br.readLine().split(" ");
long A = Long.parseLong(arr[0]);
long B = Long.parseLong(arr[1]);
boolean[] isNotPrimeNum = new boolean[10000000 + 1];
getPrimeNumArr(isNotPrimeNum, B);
int result = getNearlyPrimeNumCount(isNotPrimeNum, A, B);
System.out.println(result);
}
public static void getPrimeNumArr(boolean[] arr, long max) {
arr[0] = arr[1] = true;
for (int i = 2; i<=10000000; i++) {
if (!arr[i]) {
for (int j = i+i; j<=10000000; j+=i) {
arr[j] = true;
}
}
}
}
public static int getNearlyPrimeNumCount(boolean[] isNotPrimeNum, long min, long max) {
int count = 0;
for (int i=2; i< isNotPrimeNum.length; i++) {
if (!isNotPrimeNum[i]) {
long temp = i;
long curr = i;
while ((double)curr <= (double)max/(double)temp) {
if ((double)curr >= (double)min/(double)temp) {
count++;
}
temp *= curr;
}
}
}
return count;
}
}
|
cs |
틀리는 이유 = double형이 아니기 때문에 나누기의 결과가 정확하지 않다.
따라서 5 5가 입력되었을 때 2에서
2 <= 2/2 {
( 2>= 2/2) {
1++
}
}
라는 황당한 결과가 도출된다.
그렇다..
에휴.. ㅎㅎ
간만에 알고리즘 풀고 현타오는구만
'CS ﹒ Algorithm > Baekjoon' 카테고리의 다른 글
| 백준 Java 문제풀이 (62) 1747_소수 & 팰린드롬 수 중에서 최솟값 찾기 (0) | 2022.11.09 |
|---|---|
| Java 백준 문제풀이 (60) 1541_잃어버린 괄호 (0) | 2022.11.03 |
| Java 백준 문제풀이 (59) 1931 _ 회의실 배정 (0) | 2022.11.02 |
| Java 백준 문제풀이 (58) 1744 _ 수 묶기 (0) | 2022.10.29 |
| Java 백준 문제풀이 (58) 1715 _ 카드 정렬하기 (0) | 2022.10.29 |
