문제 링크
(2024/9/10 기준) Gold V

문제 읽기

$1$부터 $N$까지의 자연수를 색칠해야 합니다. 단, 서로소인 두 자연수는 서로 다른 색으로 칠해야 하고, 최소한의 색을 사용해야 합니다.

예시

$n=5$일 때, $1\ 2\ 3\ 4\ 5$를 $\color{salmon}1\ \color{sandybrown}2\ \color{seagreen}3\ \color{sandybrown}4\ \color{skyblue}5$로 $4$가지 색을 이용하여 색칠할 수 있습니다. 따라서, 정답은 $1\ 2\ 3\ 2\ 4$입니다. (색의 순서는 상관이 없습니다. 최소 개수를 만족하기만 한다면 정답으로 인정됩니다. 또한, $6$을 $2$와 같은 색으로 칠하든 $3$과 같은 색으로 칠하든 모두 정답으로 인정됩니다.)

풀이

일단, $1$은 모든 자연수와 서로소입니다. 따라서, $1$은 $1$을 제외한 자연수와 다른 색으로 칠해야 합니다. 또한, 서로 다른 두 소수 $p_1$, $p_2$는 서로소이므로, 다른 색으로 칠해야 합니다. 만약, 합성수 $C$가 자신의 소인수에 칠해진 색과 다른 색으로 칠해진다면, 서로소인 두 자연수를 같은 색으로 칠하게 되거나, 그렇지 않으면 불필요한 색이 하나가 늘어나므로, 최소한의 색으로 색칠할 수 없습니다. 따라서, $N$이하의 소수 $p$ 각각에 대하여, $p$와 $p$의 모든 배수들끼리 같은 색으로 칠한다면 최소한의 개수의 색으로 칠할 수 있게 됩니다.

이때, 소수와 그 배수들을 다루는 방법이 하나 있습니다. 바로 에라토스테네스의 체 입니다. 에라토스테네스의 체의 일반적인 구현은 bool배열을 이용하는 것인데, bool 대신 int배열을 사용하여 $k$번째 소수와 그 배수들을 모두 $k + 1$로 업데이트하면 됩니다. ($1$도 색칠해야 하므로, $2$가 첫 번째 소수이지만, $2$번째 색이 됩니다.)

그렇다면, 색의 개수의 최솟값은 어떻게 알 수 있을까요? $1$부터 $N$까지 임의의 소수 $p$와 그 배수들이 모두 한 가지 동일한 색으로 칠해지므로, $N$이하의 소수의 개수만 알면 됩니다. 즉, $(N$ 이하의 소수의 개수$) + 1$개 의 색으로 칠할 수 있고, 이것이 최소라는 결론이 자연스럽게 도출됩니다.

해당 풀이의 시간복잡도는 에라토스테네스의 체와 동일한 $\mathcal{O}(N\lg(\lg N))$입니다. (여기서 $\lg$는 밑이 $2$인 이진로그입니다.) 따라서, $N \leq 500\ 000$이므로, 충분히 제한 시간 $1$초 내에 동작합니다.

후기

매우 직관적이고 쉬운 문제지만, 에라토스테네스의 체의 작동 방식에 대한 정확한 이해 없이는 풀기 어려운 문제 같습니다.