C++로 원소와 합이 모두 x로 나누어 떨어지는 부분집합 개수 구하기

문제 설명

숫자 배열 arr[]와 정수 x가 입력으로 주어졌을 때, 부분집합에 포함된 개별 원소와 그 원소들의 합이 모두 x로 완전히 나누어 떨어지는 모든 부분집합의 개수를 구하는 것이 목표입니다.

예시 1

입력

arr[] = {1,2,3,4,5,6}, x = 3

출력

주어진 조건을 만족하는 부분집합의 개수 : 3

설명

[3], [6], [3,6]

x가 3일 때 배열에서 3으로 나누어 떨어지는 원소는 3과 6뿐입니다. 이 원소들로 만들 수 있는 부분집합은 [3], [6], [3,6]의 세 가지이며, 각 원소와 그 합(9) 모두 3으로 나누어 떨어지므로 조건을 만족합니다.

예시 2

입력

arr[] = {1,2,3,4,5,6}, x = 4

출력

주어진 조건을 만족하는 부분집합의 개수 : 1

설명

[4]

x가 4일 때 4로 나누어 떨어지는 원소는 4 하나뿐이므로, 조건을 만족하는 부분집합은 [4] 하나입니다.

접근 방법

핵심 아이디어는 의외로 간단합니다. 어떤 수 a가 x로 나누어 떨어진다면, 그 수 하나만으로 이루어진 부분집합도 조건을 만족하고, x로 나누어 떨어지는 수들을 더한 합 역시 x로 나누어 떨어집니다. 반면 x로 나누어 떨어지지 않는 원소는 단독으로도, 다른 원소와의 합으로도 조건을 충족할 수 없기 때문에 부분집합에 포함될 수 없습니다.

따라서 다음 순서로 문제를 해결할 수 있습니다.

배열 arr[]에서 x로 나누어 떨어지는 원소의 개수를 셉니다(count).
각 원소는 부분집합에 '포함되거나 포함되지 않거나' 두 가지 선택지가 있으므로, 전체 경우의 수는 2^count입니다.
공집합은 조건에서 제외해야 하므로, 최종 답은 2^count − 1이 됩니다.

특별한 경우로, x가 1이면 모든 원소가 나누어 떨어지므로 전체 원소 개수 n에 대해 2ⁿ − 1을 바로 반환하면 됩니다.

C++ 구현 예제

#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int sub_sets(int arr[], int size, int val){
    int count = 0;
    if (val == 1){
        count = pow(2, size) - 1;
        return count;
    }
    for (int i = 0; i < size; i++){
        if (arr[i] % val == 0){
            count++;
        }
    }
    count = pow(2, count) - 1;
    return count;
}
int main(){
    int arr[] = { 4, 6, 1, 3, 8, 10, 12 }, val = 4;
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"주어진 조건을 만족하는 부분집합의 개수 : "<<sub_sets(arr, size, val);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

주어진 조건을 만족하는 부분집합의 개수 : 7

배열 {4, 6, 1, 3, 8, 10, 12}에서 4로 나누어 떨어지는 원소는 4, 8, 12로 세 개입니다. 따라서 2³ − 1 = 7개의 부분집합이 조건을 만족하게 됩니다. 이처럼 모든 부분집합을 일일이 탐색하는 대신 나누어 떨어지는 원소의 개수만 세면 되므로, 시간 복잡도는 O(n)으로 매우 효율적입니다.