제2회 곰곰컵 풀이

A - 치킨댄스를 추는 곰곰이를 본 임스 2 풀이
B - 붙임성 좋은 총총이 풀이
C - 곰곰이와 학식 풀이
D - 오락실에 간 총총이 풀이
E - 곰곰이와 시소 풀이
F - 외로운 곰곰이는 친구가 있어요 풀이
G - 곰곰이와 테트리스 풀이
H - 곰곰아 선 넘지마 풀이
I - 곰곰이의 식단 관리 2 풀이
J - 서커스 나이트 풀이

BOJ 26077 - 서커스 나이트 링크
(2022.12.02 기준 G1)

문제

N마리의 돌고래가 있고, 각 돌고래는 양의 정수인 ID가 있다.
각 돌고래는 자신의 ID의 1이 아닌 약수 만큼의 주파수를 발생시켜 메시지를 전달할 수 있고, 또한 자신의 ID의 1이 아닌 약수만큼 발생하는 주파수를 통한 메시지를 들을 수 있다.
자신이 들은 메시지는 다시 다른 돌고래들에게 전달할 수 있을 때, 각 돌고래가 메시지를 전달할 때 전달받을 수 있는 돌고래 수의 최댓값 출력

알고리즘

각 돌고래마다 ID가 부여되므로 그 ID를 이용해 Union-Find를 이용하면 된다.

풀이

누구나 생각할 수 있는 방법은 돌고래의 모든 쌍마다 GCD가 2 이상이면 Union 하는 방법이다.
하지만 N이 최대 1,000,000 이므로 TLE가 발생한다.

그럼 이렇게 생각해보자.
각 돌고래의 ID마다 소인수분해를 해보자. 그리고 2 이상의 약수들을 ID와 Union 해서 묶어버리는 것이다. 이를 모든 돌고래마다 해보자.
그러면 소인수들을 통해 묶일 돌고래들은 간접적으로 묶이게 되는 것이다.

그런데 또 문제가 있다.
일반적인 에라토스테네스의 체를 이용하여 소수를 저장하고, 그 소수들을 통해 일일이 나눠지는지 확인하며 소인수분해를 하면 TLE가 발생한다.

보통 체로 거를 때, bool로 한다. 하지만 다르게 생각을 해보자.

factor = list(range(1000001))
for i in range(2, int(1000000 ** 0.5) + 1):
    if factor[i] == i:
        for j in range(i * 2, 1000001, i):
            if factor[j] == j:
                factor[j] = i

모든 수마다 2 이상의 나눠지는 최소 약수를 저장하는 것이다.
그러면 소인수분해를 할 때마다, 1이 될 때까지 저장되어 있는 수로 나눠주기만 하면 되는 것이다.

코드

import sys; input = sys.stdin.readline
from collections import defaultdict

def find(u):
    if parent[u] != u:
        parent[u] = find(parent[u])
    return parent[u]

def union(u, v):
    u = find(u)
    v = find(v)
    if u < v:
        parent[v] = u
    else:
        parent[u] = v

# 에라토스테네스의 체를 이용하여 2 이상의 최소 약수를 저장
factor = list(range(1000001))
for i in range(2, int(1000000 ** 0.5) + 1):
    if factor[i] == i:
        for j in range(i * 2, 1000001, i):
            if factor[j] == j:
                factor[j] = i


N = int(input())
ID = list(map(int, input().split()))

# 각 ID마다 소인수분해를 하면서 나오는 소인수들과 ID를 Union
parent = list(range(1000001))
for id in ID:
    n = id
    while n > 1:
        union(id, factor[n])
        n //= factor[n]

# 각 ID의 루트(부모) 값에 +1
# 맵를 이용하면 조금 더 빠르다.
result = defaultdict(int)
for id in ID:
    result[find(id)] += 1
print(max(result.values()))