[BOJ/Gold 5] 백준 23048 자연수 색칠하기(C++)

문제 링크

https://www.acmicpc.net/problem/23048

23048번: 자연수 색칠하기

 

 

문제

 1부터 N까지의 자연수를 색칠한다. 단, 서로소인 서로 다른 두 자연수는 다른 색으로 칠해야 한다. 최소한의 색을 써서 모든 자연수를 칠하는 방법을 찾는 프로그램을 작성하자.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000)

출력

첫째 줄에 사용한 색의 수 K를 출력한다.

둘째 줄에 N개의 수를 공백을 사이에 두고 출력한다. i번째 수는 자연수 i의 색이다. 색은 1 이상 K 이하의 정수로 나타낸다.

예제 입력 1

5

예제 출력 1

4
1 2 3 2 4

노트

다음은 N = 5일 때의 올바른 색칠과 올바르지 않은 색칠의 예시다.

첫 번째 색칠은 올바른 색칠이다. 2와 4는 같은 색으로 색칠했지만, 서로소가 아니므로 문제의 조건에 위배되지 않는다. 또한, 5까지의 자연수를 색칠하기 위해 최소 4개의 색이 필요함을 증명할 수 있다.

두 번째 색칠은 서로소인 2와 3이 같은 색으로 칠해졌기 때문에 올바르지 않은 색칠이다.

세 번째 색칠은 최소한의 색깔로 칠하지 않았기 때문에 올바르지 않은 색칠이다.

알고리즘 분류

• 소수 판정

풀이

에라토스테네스의 체를 통해 소수를 판정한다.

이후 숫자 1은 색깔 1로 칠한 후, 숫자 2부터 순차적으로 소수이면 새로운 색깔로 칠한 후, 해당 숫자의 배수들을 전부 같은 색깔로 칠한다.

코드

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#define MAX 500001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N;
int DP[MAX];
int K = 2;
int Color[MAX];

void init() {
    Color[1] = 1;
    for (int i = 2; i <= (MAX - 1); i++) {
        DP[i] = i;
    }
    for (int i = 2; i <= sqrt(MAX - 1); i++) {
        if (DP[i] == 0) {
            continue;
        }
        for (int j = (i * i); j <= (MAX - 1); j += i) {
            DP[j] = 0;
        }
    }
}

void input() {
    cin >> N;
}

void settings() {
    for (int i = 2; i <= N; i++) {
        if (DP[i] != 0) {
            Color[i] = K;
            if (i <= sqrt(N)) {
                for (int j = (i * i); j <= N; j += i) {
                    Color[j] = K;
                }
            }
            K++;
        }
    }
}

void find_Answer() {
    cout << K - 1 << "\n";
    for (int i = 1; i <= N; i++) {
        cout << Color[i] << " ";
    }
    cout << "\n";
}

int main() {
    FASTIO
    init();
    input();
    settings();
    find_Answer();

    return 0;
}