C++로 부분집합 차이의 합계 구하기: 효율적인 알고리즘과 코드 예제

이 문제에서는 n개의 숫자로 이루어진 집합 S가 주어지며, 각 부분집합의 마지막 원소와 첫 번째 원소의 차이를 모두 더한 값, 즉 부분집합 차이의 합계를 구하는 프로그램을 작성해야 합니다.

계산 공식은 다음과 같습니다.

sumSubsetDifference = Σ [last(s) - first(s)]
여기서 s는 집합 S의 부분집합입니다.

문제 이해를 위한 예제

입력 −

S = {1, 2, 9}, n = 3

출력 − 24

설명 − 모든 부분집합은 다음과 같습니다.

{1}, last(s) - first(s) = 0
{2}, last(s) - first(s) = 0
{9}, last(s) - first(s) = 0
{1, 2}, last(s) - first(s) = 1
{1, 9}, last(s) - first(s) = 8
{2, 9}, last(s) - first(s) = 7
{1, 2, 9}, last(s) - first(s) = 8
합계 = 1 + 8 + 7 + 8 = 24

이 문제를 푸는 가장 단순한 방법은 모든 부분집합에 대해 마지막 원소와 첫 번째 원소의 차이를 구한 뒤 이를 모두 더하는 것입니다. 하지만 이 방법은 효율성이 떨어지므로, 더 효율적인 접근 방식을 살펴보겠습니다.

n개의 원소를 가진 집합 S의 경우, 각 원소에서 시작하는 부분집합의 개수를 이용해 합계를 계산한 후 이를 모두 더하면 결과를 구할 수 있습니다.

즉,

sumSetDifference(S) = Σ [Σlast(s) - Σfirst(s)]

원소 {s1, s2, s3, …, sn}으로 구성된 집합 S를 생각해 봅시다.

s1에서 시작하는 부분집합은 {s2, s3, …, sn}의 원소들을 조합하여 만들 수 있으며, 이 경우 2^n-1개의 부분집합이 만들어집니다.

마찬가지로 s2에서 시작하는 부분집합은 2^n-2개입니다.

이를 일반화하면, Si에서 시작하는 부분집합의 개수는 2^n-i개입니다.

따라서 모든 부분집합의 첫 번째 원소의 합은 다음과 같습니다.

SumFirst = a1·2^n-1 + a2·2^n-2 + a3·2^n-3 + … + an·2^n-n

같은 방식으로 마지막 원소를 고정하여 SumLast를 계산합니다.

SumLast = a1·2^n-n + a2·2^n-(n-1) + a3·2^n-(n-2) + … + an·2^n-(n-(n-1))

예제 코드

위에서 설명한 해결 방법을 구현한 프로그램입니다.

#include<iostream>
#include<math.h>
using namespace std;
int CalcSumFirst(int S[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum = sum + (S[i] * pow(2, n-i-1));
    return sum;
}
int CalcSumLast(int S[], int n) {
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum = sum + (S[i] * pow(2, i));
    return sum;
}
int main() {
    int S[] = {1, 4, 9, 6};
    int n = 4;
    int sumSetDiff = CalcSumLast(S, n) - CalcSumFirst(S, n);
    printf("The sum of subset differences is %d", sumSetDiff);
    return 0;
}

출력

The sum of subset differences is 45