C++ 조합론

집합 N

N = { 2, 3, 4 }

 

N의 부분집합을 S라고 할 때,

S의 모든 원소의 곱의 합을 구하는 방법

 

S = { 2 }, { 3 }, { 4 }, { 2, 3 }, { 2, 4 }, { 3, 4 }, { 2, 3, 4 }

 

1. 원소 개수가 1개인 경우

-> 2 + 3 + 4 = 9

 

2. 원소 개수가 2개인 경우

-> 2 * 3 + 2 * 4 + 3 * 4 = 26

 

3. 원소 개수가 3개인 경우

-> 2 * 3 * 4 = 24

 

모두 더하면 59가 된다

 

이를 간단히 구해보자

 

원소 2, 3, 4를 각각 X, Y, Z라고 하면

 

모든 원소의 곱의 합은

X + Y + Z + XY + XZ + YZ + XYZ가 된다 (곱하기 기호 생략)

즉, ( X + 1 ) * ( Y + 1 ) * ( Z + 1 ) - 1이 되므로,

 

이는 간단하게 ( X + 1 ) * ( Y + 1 ) * ( Z + 1 ) - 1 의 결과로 구할 수 있다

 

앞서 들었던 예시인 N의 경우로 살펴보면,

( 2 + 1) * ( 3 + 1 ) * ( 4 + 1 ) - 1

= 3 * 4 * 5 - 1 = 59이다.

 

적용 가능한 예제는 

백준 9375번 https://www.acmicpc.net/problem/9375 이 있다.