시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 448 | 146 | 115 | 32.764% |
$1$부터 $N$까지의 자연수를 색칠한다. 단, 서로소가 아닌 서로 다른 두 자연수는 다른 색으로 칠해야 한다. 최소한의 색을 써서 모든 자연수를 칠하는 방법을 찾는 프로그램을 작성하자.
첫째 줄에 자연수 $N$이 주어진다. ($1 \le N \le 500\,000$)
첫째 줄에 사용한 색의 수 $K$를 출력한다.
둘째 줄에 $N$개의 수를 공백을 사이에 두고 출력한다. $i$번째 수는 자연수 $i$의 색이다. 색은 $1$ 이상 $K$ 이하의 정수로 나타낸다.
5
2 1 1 1 2 1