C++에서 합이 3의 배수가 되는 크기 2 또는 3 그룹의 개수 구하기

개요

이 튜토리얼에서는 주어진 정수 배열에서 합이 3의 배수가 되는 크기 2 또는 크기 3의 그룹이 총 몇 개 존재하는지 구하는 프로그램을 작성해 보겠습니다.

접근 방식

모든 조합을 일일이 검사하는 대신, 각 원소를 3으로 나눈 나머지를 활용하면 효율적으로 문제를 해결할 수 있습니다. 어떤 수들의 합이 3의 배수가 되려면, 그 수들을 3으로 나눈 나머지의 합 역시 3의 배수여야 하기 때문입니다.

먼저 배열의 모든 원소를 순회하면서 나머지가 0, 1, 2인 원소의 개수를 각각 세어 배열 c에 저장합니다. 이후 다음 조합들의 개수를 모두 더해 최종 결과를 얻습니다.

• 크기 2 그룹: 나머지가 0인 두 원소의 조합 C(c[0], 2), 나머지가 1과 2인 원소를 하나씩 선택하는 조합 c[1] × c[2]
• 크기 3 그룹: 나머지가 서로 같은 세 원소의 조합 C(c[i], 3) (i = 0, 1, 2), 그리고 나머지가 0, 1, 2인 원소를 하나씩 선택하는 조합 c[0] × c[1] × c[2]

예제 코드

#include<bits/stdc++.h>
using namespace std;

// 합이 3의 배수가 되는 크기 2 또는 3 그룹의 개수 반환
int count_groups(int arr[], int n){
    int c[3] = {0}, i;
    int res = 0;
    // 나머지별 원소 개수 카운트
    for (i = 0; i < n; i++)
        c[arr[i]%3]++;
    // 크기 2 그룹: (0,0)과 (1,2) 조합
    res += ((c[0]*(c[0]-1))>>1);
    res += c[1] * c[2];
    // 크기 3 그룹: (0,0,0), (1,1,1), (2,2,2), (0,1,2) 조합
    res += (c[0] * (c[0]-1) * (c[0]-2))/6;
    res += (c[1] * (c[1]-1) * (c[1]-2))/6;
    res += ((c[2]*(c[2]-1)*(c[2]-2))/6);
    res += c[0]*c[1]*c[2];
    return res;
}

int main(){
    int arr[] = {3, 6, 7, 2, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Required number of groups are " << count_groups(arr,n) << endl;
    return 0;
}

실행 결과

Required number of groups are 8

코드 설명

예제 배열 {3, 6, 7, 2, 9}를 살펴보면, 각 원소를 3으로 나눈 나머지는 차례대로 0, 0, 1, 2, 0입니다. 따라서 c[0] = 3, c[1] = 1, c[2] = 1이 됩니다.

• 크기 2 그룹: C(3, 2) + 1 × 1 = 3 + 1 = 4개
• 크기 3 그룹: C(3, 3) + 3 × 1 × 1 = 1 + 3 = 4개

두 값을 합하면 총 8개의 그룹이 도출되며, 이는 프로그램의 실행 결과와 일치합니다.

이 알고리즘은 배열을 한 번만 순회하면 되므로 시간 복잡도는 O(n)이고, 추가로 사용하는 메모리는 상수 크기의 배열 하나뿐이므로 공간 복잡도는 O(1)입니다. 브루트 포스 방식(O(n²), O(n³))과 비교했을 때 훨씬 효율적인 접근법입니다.