C++로 배열 요소를 최소 색상 수로 칠하는 방법

문제 설명

n개의 요소를 가진 배열 A가 있다고 가정해 보겠습니다. 우리는 다음 두 조건을 만족하도록 배열의 요소들을 색칠해야 합니다.

• 어떤 색상이든, 그 색상으로 칠해진 모든 요소는 반드시 같은 색상 그룹 내 최솟값으로 나누어 떨어져야 합니다.
• 사용되는 색상의 개수는 가능한 한 최소화해야 합니다.

즉, 주어진 모든 숫자를 유효한 방식으로 칠하기 위해 필요한 최소 색상 수를 구하는 것이 목표입니다.

예를 들어 입력이 A = [10, 2, 3, 5, 4, 2]라고 한다면, 정답은 3이 됩니다. 첫 번째 색상은 A[0](10)과 A[3](5)에, 두 번째 색상은 A[2](3)에, 세 번째 색상은 나머지 세 요소(2, 4, 2)에 사용되기 때문입니다.

풀이 접근 방법

이 문제의 핵심 아이디어는 간단합니다. 먼저 배열을 오름차순으로 정렬한 뒤, 각 요소가 자신보다 앞에 있는 요소들 중 하나라도 나누어 떨어지는지 확인합니다.

• 앞선 어떤 요소로도 나누어 떨어지지 않는다면 → 새로운 색상이 필요합니다.
• 앞선 요소 중 하나로 나누어 떨어진다면 → 해당 요소가 속한 색상 그룹에 함께 칠할 수 있으므로 기존 색상을 재사용합니다.

배열이 정렬되어 있기 때문에 각 그룹의 최솟값은 항상 그룹에서 가장 먼저 등장한 요소가 되며, 따라서 위 조건 검사만으로 올바른 답을 구할 수 있습니다.

알고리즘 단계

n := 배열 A의 크기
ans := 0
배열 A를 오름차순 정렬
i := 0부터 n-1까지 반복:
    ok := 1
    j := 0부터 i-1까지 반복:
        ok := ok AND (A[i]를 A[j]로 나눈 나머지가 0이 아니면 1, 아니면 0)
    ans := ans + ok
ans 반환

이 알고리즘의 시간 복잡도는 이중 반복문 때문에 O(n²)입니다.

C++ 구현 예제

아래 구현 예제를 통해 더 쉽게 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A)
{
    int n = A.size();
    int ans = 0;
    sort(A.begin(), A.end());
    for (int i = 0; i < n; i++)
    {
        int ok = 1;
        for (int j = 0; j < i; j++)
        ok &= (A[i] % A[j] != 0);
        ans += ok;
    }
    return ans;
}
int main()
{
    vector<int> A = { 10, 2, 3, 5, 4, 2 };
    cout << solve(A) << endl;
}

입력

{ 10, 2, 3, 5, 4, 2 }

출력

3