26077 - 서커스 나이트
본문
서커스를 보고 온 곰곰이는 돌고래들의 의사소통 체계를 이해하게 되었다고 한다. 곰곰이는 신난 표정으로 자신이 알게 된 내용을 당신에게 설명해 주고 있다.
돌고래들의 의사소통 방법:
- 각 돌고래는 양의 정수인
ID가 있고, 이ID의 $1$이 아닌 약수 만큼의 주파수를 발생시켜 메시지를 전달할 수 있다. - 또한 각 돌고래는 자신의
ID의 $1$이 아닌 약수만큼 발생하는 주파수를 통한 메시지를 들을 수도 있다. - 돌고래는 자신이 들은 메시지를 다시 다른 돌고래들에게 전달할 수 있다.
이야기를 들은 당신은 아래와 같은 궁금증이 생겼다.
- $N$마리의 돌고래가 있고, 이들의
ID가 주어진다. $i\ (1 \le i \le N)$번째 돌고래에게 최초로 메시지를 주며 다른 돌고래들에게 전파해달라고 부탁했을 때, 메시지를 전달받을 수 있는 돌고래 수의 최댓값을 $k_i$라 하자. 이 때, $max(k_1, k_2, \cdots, k_N)$의 값은 무엇인가?
$N$마리의 돌고래들의 ID가 주어졌을 때 이 질문에 대한 답을 해보자.
입력
첫째 줄에 정수 $N$이 주어진다. ($1 \le N \le 1\ 000\ 000$)
둘째 줄에 공백을 사이에 두고 $N$마리 돌고래의 ID가 주어진다. ($2 \leq$ ID $ \le 1\ 000\ 000$, ID는 정수)
출력
지문에서 설명된 $max(k_1, k_2, \cdots, k_N)$의 값을 출력하라.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 1sec | 1024MB |
풀이
문제풀 때 생각이 짧았던 문제다. 디버그에서도 원인을 찾지 못해서 삽질을 수차례 해버렸다. 결국 12트..
가장 먼저 고려해야할 것은 시간제한이다. 입력으로 주어지는 수는 총 100만개. 이것을 1초안에 돌리려면 최악일 때 원소마다 탐색하는 값의 수가 100개 미만이어야한다. $O(n^2)$으로는 택도 없고, $O(n \sqrt n)$도 불가능.
생각할 수 있는 방법은 소수를 활용하는 것. 어떤 수의 약수를 찾을건데, 같은 수에서 나오는 약수는 모두 같은 그룹으로 묶일 수 있기 때문에, 소인수의 그룹만 만들어두면 된다는 생각을 할 수 있다. 그래서 소수를 먼저 계산해두는 것이 좋다. 다만 그 값이 문제인데, 1부터 100만 사이의 소수 개수는 약 78500개. 수가 터무니없이 만다. 다행인 것은 “어떤 수가 소수인지 판별하기 위해서는 그 수의 제곱근까지만 탐색하면 된다”는 점이다. 1부터 1000까지의 소수의 개수는 167개. 범위를 넘긴 하는데 마땅한 방법이 떠오르지는 않으므로 일단 이대로 진행한다. 사실 최악으로 만든다면 1백만개의 데이터가 모두 997을 소인수로 가지면 내 방법으로는 시간초과가 날 것 같다.
그룹을 하나로 묶어서 관리해야하므로, 분리 집합 방법을 사용할 수 있다. 그룹은 입력되는 수들만큼 생성하고, 본인의 소인수만 합쳐주는걸로 하였다. 예를 들어 입력된 값 $a$가 $4$를 약수로 가진다고 하여도, 그것은 $2$를 계산할 때 이미 고려될 것이므로, 무시하는 것이다. 이렇게 하면 관리해야할 그룹의 수도 줄어든다는 장점이 있다.
특정한 수가 2개 이상의 소인수를 가진다면, 두 그룹을 합쳐주어야한다. 이 때 그룹 내에 속한 원소값의 개수도 세어야하는데, 헷갈리지 않기 위해서 parent가 작은 그룹으로 다른 그룹을 합치기로 하였다. 합치면서 개수도 합쳐주도록 하자. 모든 계산이 끝난 이후 그룹에 현재 입력된 값을 추가하여 중복으로 세는 것을 방지한다.
여기서 내가 삽질한 부분이 나온다. 코드 기준 88번째 줄이 있는 블럭인데, 1부터 1000까지 모든 소수에 대해 계산이 끝난 이후에도 $a$에 값이 남아있을 수가 있었다. if 안에 속한다면 $a$가 1000보다 큰 소수, else에 속한다면 1000보다 큰 소수를 포함하는 합성수라는 사실을 간과했다. 그래서 1001같은 입력이 들어왔을 때 제대로 처리할 수 없었던 것이다. 이 부분도 하나의 그룹이라고 생각해야하고, 합쳐주는 과정을 거쳐야한다. 그룹의 개수를 소수의 개수가 아니라 입력으로 가능한 숫자 전부로 지정해둔 이유기도 하다. 이러는게 안헷갈리니까..
코드
사용 언어 : C
최종 수정일 : 2023 / 4 / 7
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <stdio.h>
typedef char bool;
const bool true = 1;
const bool false = 0;
#define MAX_IDX (int)(1e6 + 1)
int parent[MAX_IDX];
int cnt[MAX_IDX];
int n;
#define MAX_PRIME 1000
bool isNotPrime[MAX_PRIME + 1];
int prime[MAX_PRIME];
int primeLen = 0;
void primeInit() {
isNotPrime[0] = isNotPrime[1] = true;
for (int i = 2; i < MAX_PRIME; ++i) {
if (isNotPrime[i] == false) {
prime[primeLen++] = i;
for (int j = i * 2; j < MAX_PRIME; j += i) {
isNotPrime[j] = true;
}
}
}
return;
}
void disjointInit() {
for (int i = 2; i < MAX_IDX; ++i) {
parent[i] = i;
cnt[i] = 0;
}
return;
}
int find(int x) {
if (parent[x] == x) {
return x;
} else {
return parent[x] = find(parent[x]);
}
}
int merge(int a, int b) {
int x = find(a), y = find(b);
if (x == y) {
return x;
} else if (x > y) {
int temp = a;
a = b, b = temp;
temp = x;
x = y, y = temp;
}
cnt[x] += cnt[y];
parent[y] = parent[b] = x;
return x;
}
#define max(a, b) (((a) > (b)) ? (a) : (b))
const int NOTYET = -1;
int result = 0;
int main() {
primeInit();
disjointInit();
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
int a;
scanf("%d", &a);
int divider = NOTYET;
for (int j = 0; j < primeLen; ++j) {
if (a % prime[j] == 0) {
if (divider == NOTYET) {
divider = prime[j];
} else {
divider = merge(divider, prime[j]);
}
while (a % prime[j] == 0) {
a /= prime[j];
}
}
}
if (a > 1) {
if (divider == NOTYET) {
divider = a;
} else {
divider = merge(divider, a);
}
}
divider = find(divider);
++cnt[divider];
result = max(result, cnt[divider]);
}
printf("%d", result);
return 0;
}