24441 - 행운 수 판정
본문
행운 수(Lucky numbers)는 에라토스테네스의 체와 비슷한 방법으로 만들어지는 자연수의 부분집합 또는 그 부분집합의 원소를 말한다.
행운 수의 집합은 다음과 같은 과정을 통해 구성할 수 있다.
- 홀수 자연수의 목록을 만든다.
- 목록에 속한 수 중 $1$보다 크면서 선택한 적이 없는 수 중에서 가장 작은 수를 선택한다.
- 2.에서 선택한 자연수를 $k$라고 할 때, 목록에서 오름차순으로 $i \times k$ ($i \geq 1$) 번째에 해당하는 모든 자연수를 지운다.
- 2.로 돌아간다.
다음은 위 과정의 일부를 수행하는 예시이다.
- $1$ $3$ $5$ $7$ $9$ $11$ $13$ $15$ $17$ $19$ $21$ $23$ $25$ $\cdots$
- $1$ $\underline{\textbf{3}}$ $5$ $7$ $9$ $11$ $13$ $15$ $17$ $19$ $21$ $23$ $25$ $\cdots$
- $1$ $3$ $\cancel{5}$ $7$ $9$ $\cancel{11}$ $13$ $15$ $\cancel{17}$ $19$ $21$ $\cancel{23}$ $25$ $\cdots$
- $1$ $3$ $7$ $9$ $13$ $15$ $19$ $21$ $25$ $\cdots$
- $1$ $3$ $\underline{\textbf{7}}$ $9$ $13$ $15$ $19$ $21$ $25$ $\cdots$
- $1$ $3$ $7$ $9$ $13$ $15$ $\cancel{19}$ $21$ $25$ $\cdots$
- $1$ $3$ $7$ $9$ $13$ $15$ $21$ $25$ $\cdots$
- $1$ $3$ $7$ $\underline{\textbf{9}}$ $13$ $15$ $21$ $25$ $\cdots$
- $\cdots$
자연수 $n$이 주어지면 $n$이 행운 수인지 아닌지 알아보자.
입력
첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \leq T \leq 10\,000 = 10^4$)
각 테스트 케이스는 한 줄로 이루어져 있으며, 자연수 $n$이 주어진다. ($1 \leq n \leq 1\,000\,000 = 10^6$)
출력
각 테스트 케이스마다 $n$이 행운 수이면 “lucky”를, $n$이 행운 수가 아니면 “unlucky”를 큰따옴표 없이 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 3sec | 1024MB |
풀이
행운 수라는 것들은 이미 정의되어 있다. 입력 $n$이 달라진다고 해서 행운 수가 달라지지는 않는다. 즉 답을 미리 계산해두는 것이 가능하다는 것. 숫자의 범위가 크지 않기 때문에, 쿼리 시작 전에 모든 행운 수를 미리 찾아서 기록해두도록 하자.
행운 수를 찾는 함수로 getLuckyNumber()라는 함수를 만들자. 이 함수는 $1$부터 $1\,000\,000$까지의 행운 수를 모두 찾는 함수이다. 이 함수 자체가 돌아가는 과정이 3초를 넘기 때문에, 결과값은 문자열로 출력하여 다른 프로그램에서 문자열만 읽어도 이전의 결과를 기록할 수 있도록 하자. 그럼 이 함수는 시간에 구애받지 않고 구현해도 되므로, $O(n^2)$ 완전탐색으로 구현해도 크게 문제되지 않는다.
사용 언어 : C
최종 수정일 : 2023 / 6 / 22
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
void get_init() {
for (int i = 1; i < n; ++i) {
arr[i] = i * 2 - 1;
}
return;
}
int getLuckyNumber() {
get_init();
for (int i = 2; i < n; ++i) {
int k = arr[i];
printf("Lucky Number : %d\n", k);
if (k == 0) {
break;
}
top = 1;
for (int j = 1; j < n; ++j) {
if (j % k != 0) {
tempArr[top++] = arr[j];
}
}
for (int j = 0; j < top; ++j) {
arr[j] = tempArr[j];
}
for (int j = top; j < n; ++j) {
arr[j] = 0;
}
}
FILE* f = fopen("input.txt", "w");
for (int i = 0; i < top; ++i) {
if (arr[i] > 0) {
fprintf(f, "%d,", arr[i]);
}
}
fclose(f);
return 0;
}
이러면 “input.txt” 파일에는 모든 행운 수가 적힌 문자열이 만들어진다. 앞부분만 조금 떼보면 1,3,7,9,13,15,21,25,31,33,37,43,49,51,63,67, 식으로 작성되는 것이다. 이것을 코드에 다시 넣고 숫자들만 뽑아내어 행운 수로 활용하면 된다. 활용하는 방법으로는 아래와 같은 방법을 사용했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void init() {
int temp = 0;
for (int i = 0; resultString[i] != '\0'; ++i) {
switch (resultString[i]) {
case ',': {
isLuckyNumber[temp] = true;
temp = 0;
break;
}
default: {
temp *= 10;
temp += (resultString[i] - '0');
}
}
}
return;
}
그러면 isLuckyNumber[]은 index가 행운 수인지 아닌지로 표기하게 된다. 나머지는 쿼리 $q$에 따라 isLuckyNumber[q]를 출력하면 끝.
- 참고 알고리즘 :
코드
사용 언어 : C
최종 수정일 : 2023 / 6 / 22
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
69
70
71
72
73
74
75
76
77
78
void get_init() {
for (int i = 1; i < n; ++i) {
arr[i] = i * 2 - 1;
}
return;
}
int getLuckyNumber() {
get_init();
for (int i = 2; i < n; ++i) {
int k = arr[i];
printf("Lucky Number : %d\n", k);
if (k == 0) {
break;
}
top = 1;
for (int j = 1; j < n; ++j) {
if (j % k != 0) {
tempArr[top++] = arr[j];
}
}
for (int j = 0; j < top; ++j) {
arr[j] = tempArr[j];
}
for (int j = top; j < n; ++j) {
arr[j] = 0;
}
}
FILE* f = fopen("input.txt", "w");
for (int i = 0; i < top; ++i) {
if (arr[i] > 0) {
fprintf(f, "%d,", arr[i]);
}
}
fclose(f);
return 0;
}
void init() {
int temp = 0;
for (int i = 0; resultString[i] != '\0'; ++i) {
switch (resultString[i]) {
case ',': {
isLuckyNumber[temp] = true;
temp = 0;
break;
}
default: {
temp *= 10;
temp += (resultString[i] - '0');
}
}
}
return;
}
int main() {
/*
getLuckyNumber();
return 0;
*/
int t;
scanf("%d", &t);
while (t--) {
int a;
scanf("%d", &a);
printf("%s\n", printTemplate[isLuckyNumber[a]]); // "yes" or "no"
}
return 0;
}
- [Hint] $1$부터 $1\,000\,000$까지 행운 수를 계산하였을 때, 그 개수는 71918개라고 한다.