포함-배제의 원리. [16565]

[1. 문제 설명]

https://www.acmicpc.net/problem/16565

---

[2. 풀이 접근]

여러 집합의 합집합의 원소 수를 셀 때,

각 집합의 크기를 더한 뒤 겹치는 부분(교집합)을 빼거나 더하는 과정을 반복하여 정확한 전체 개수를 구하는 방법.

 

가령, 1이상 100 이하의 자연수 집합에서 2 또는 3의 배수의 개수를 구해야 할 때,

2의 배수 개수를 구하고, 3의 배수를 구하여 서로 더하면,

6의 배수가 중복되어 더해진다. (교집합이 되어버림)

 

따라서, 6의 배수 개수를 전체 결과에서 빼야 정확한 개수를 구할 수 있다.

---

[3. 코드]