66. Inclusion-Exclusion Principle

포함-배제의 원리(Inclusion-Exclusion Principle)는 각 집합의 원소의 수를 이용하여 그것들의 합집합의 원소의 수를 구할 때 사용되는 원리이다. 포함-배제의 원리에 따르면 $n$개의 집합 $A_1, A_2, \ldots A_n$의 합집합의 원소의 개수는 다음과 같이 구할 수 있다.

$$\left\vert \bigcup_{i=1}^n A_i \right\vert = \sum_{I \subset U} (-1)^{\left\vert I \right\vert +1} \left\vert \bigcap_{i \in I} A_i \right\vert$$

이것을 해석하면, $n$개의 집합의 합집합의 원소의 개수는 $($집합 $1$개의 원소의 개수의 합$) - ($집합 $2$개의 교집합의 원소의 개수의 합$) + ($집합 $3$개의 교집합의 원소의 개수의 합$) -\ \ldots\ ($집합 $n$개의 교집합의 원소의 개수의 합$)$이다. 이때 가능한 모든 집합을 계산에 포함해야 한다. 간단하게 요약하면 전체집합 $U$의 모든 부분집합의 교집합의 원소의 개수를 더하거나 빼는데, 부분집합의 수가 홀수면 더하고 짝수면 빼면 된다.

 

포함-배제의 원리는 단순히 일반적인 집합의 원소의 개수를 구할 때 이외에도 유한 측도 공간에 존재하는 모든 집합에 적용할 수 있다. 예를 들어 여러 사건의 확률을 알 때 포함-배제의 원리를 이용하여 합사건의 확률을 구할 수 있다.

 

[연습문제]

 

BOJ 17436. 소수의 배수 (Gold III)

각각의 소수의 배수를 집합으로 간주하고 포함-배제의 원리를 이용해서 합집합의 원소의 수를 구한다.

 

BOJ 12944. 재미있는 숫자 놀이 (Gold I)

17436번과 비슷한데 $K$개의 수가 서로소가 아닐 수 있으므로 교집합을 구할 때의 처리가 약간 달라지며, 교집합의 원소의 수가 $0$이 되면 바로 반복을 끝내서 오버플로우가 발생하지 않게 해야 한다.

 

BOJ 1441. 나누어 질까 (Platinum V)

이번에는 구하는 범위가 $L$ 이상 $R$ 이하로 바뀌었다. 하지만 위에서 나온 방법을 $2$번 적용해서 서로 빼 주면 마찬가지로 답을 구할 수 있다.

 

→ solved.ac tag: inclusion_and_exclusion