# [Gold I] 자연수 색칠하기 2 [문제 링크](https://www.acmicpc.net/problem/23074) ## 문제 설명 <p> $1$부터 $N$까지의 자연수를 색칠한다. 단, <strong>서로소가 아닌</strong> 서로 다른 두 자연수는 다른 색으로 칠해야 한다. 최소한의 색을 써서 모든 자연수를 칠하는 방법을 찾는 프로그램을 작성하자.</p> ## 입력 <p>첫째 줄에 자연수 $N$이 주어진다. ($1 \le N \le 500\,000$)</p> ## 출력 <p>첫째 줄에 사용한 색의 수 $K$를 출력한다.</p> <p>둘째 줄에 $N$개의 수를 공백을 사이에 두고 출력한다. $i$번째 수는 자연수 $i$의 색이다. 색은 $1$ 이상 $K$ 이하의 정수로 나타낸다.</p> ## 풀이 #### 모든 짝수는 2라는 공약수를 가진다는 성질과, 모든 홀수는 붙어있는 짝수와 항상 서로소라는 성질을 이용하였다. #### 모든 짝수마다 1씩 증가시키고, 홀수는 바로 앞 짝수의 값을 출력해주었다. ex ) 1 1 1 2 2 3 3 4 4 ... ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; cout << max(n/2, 1) << '\n'; cout << "1 "; for(int i=2;i<=n;i++) { cout << i/2 << ' '; } } ```