포함 배제의 원리

만약 우리가 2, 5, 7의 배수로 이루어지고 제일 큰 값이 n을 넘지 않는 집합의 크기를 구해야 한다고 가정한다.

n을 넘지 않는 선에서

1. 2의 배수의 갯수를 더한다.
2. 5의 배수의 갯수를 더한다.
3. 7의 배수의 갯수를 더한다.

다만 여기서 겹치는 부분은 중복해서 세어졌기 때문에 빼줘야 한다.

1. 2와 5의 최소공배수의 배수 갯수를 뺀다.
2. 5와 7의 최소공배수의 배수 갯수를 뺀다.
3. 2와 7의 최소공배수의 배수 갯수를 뺀다.

그런데 이렇게 하면 2, 5, 7에 모두 포함되는 부분은 처음에 3번 더해졌지만, 이후 다시 3번 빠져서 아예 없어지게 된다.

따라서 마지막으로

1. 2와 5와 7의 최소공배수의 배수 갯수를 다시 더한다.

즉 식으로 표현하면

2의 배수
+ 5의 배수
+ 7의 배수
- 2와 5의 공배수
- 5와 7의 공배수
- 2와 7의 공배수
+ 2와 5와 7의 공배수

가 된다.

여기서 약간의 일반화를 하면

선택한 숫자의 갯수가 홀수개이면 더하고
짝수개이면 뺀다는 것을 알 수 있다.

그리고 여러 숫자의 공배수를 구해야 하기 때문에 선택된 숫자들의 최소공배수(LCM)를 구하면 된다.

예를 들어 2, 5를 선택했다면 최소공배수는 10이고,

limit // 10

을 통해 limit 이하에 존재하는 10의 배수의 갯수를 구할 수 있다.

코드

def count(limit: int) -> int:
    ans = 0

    for i in range(1, 1 << len(coins)):
        l = 1
        b = 0

        for index, coin in enumerate(coins):
            if i & (1 << index):
                l = lcm(l, coin)
                b += 1

        if b % 2:
            ans += limit // l
        else:
            ans -= limit // l

    return ans

먼저 모든 코인을 고를 수 있는 경우의 수를 bitmasking으로 만든다.

for i in range(1, 1 << len(coins)):

우리가 고를 수 있는 코인의 갯수가 m개라면 각각의 코인은

고른다 / 고르지 않는다

두 가지 상태를 가질 수 있기 때문에 총 2^m개의 경우가 존재한다.

다만 아무 코인도 고르지 않은 경우는 포함 배제의 원리에서 사용할 필요가 없기 때문에 0을 제외하고

range(1, 1 << len(coins))

로 순회한다.

예를 들어 코인이

coins = [2, 5, 7]

이라면 비트마스크는 다음과 같은 경우들을 의미한다.

001 -> 2
010 -> 5
011 -> 2, 5
100 -> 7
101 -> 2, 7
110 -> 5, 7
111 -> 2, 5, 7

이렇게 하면 포함 배제의 원리에 필요한 모든 조합을 따로 만들어주지 않아도 한번에 순회할 수 있다.

그 다음 현재 비트마스크에서 어떤 코인이 선택되었는지 확인한다.

for index, coin in enumerate(coins):
    if i & (1 << index):

index번째 비트가 켜져 있다면 해당 코인이 현재 조합에 포함되어 있다는 뜻이다.

선택된 코인들은

l = lcm(l, coin)

을 통해 계속 최소공배수를 구해준다.

예를 들어 2, 5, 7이 선택되었다면

lcm(1, 2) = 2
lcm(2, 5) = 10
lcm(10, 7) = 70

이 되어 최종적으로 70을 얻는다.

따라서

limit // l

은 limit 이하에 존재하는 선택된 모든 숫자의 공배수 갯수가 된다.

동시에

b += 1

을 통해 몇 개의 코인을 선택했는지도 센다.

앞에서 확인했듯이 포함 배제의 원리에서는

1개 선택 -> +
2개 선택 -> -
3개 선택 -> +
4개 선택 -> -
...

가 반복된다.

따라서 단순하게 선택한 코인의 갯수가 홀수인지 짝수인지만 확인하면 된다.

if b % 2:
    ans += limit // l
else:
    ans -= limit // l

이렇게 모든 부분집합에 대해 계산하면 최종적으로 ans에는

limit 이하에서 적어도 하나의 coin의 배수인 숫자의 갯수

가 들어가게 된다.

시간복잡도

코인의 갯수를 m이라고 하면 부분집합의 갯수는

2^m - 1

개이다.

그리고 각각의 부분집합마다 최대 m개의 코인을 확인하기 때문에 이 코드의 시간복잡도는

O(m * 2^m)

이 된다.

코인의 갯수가 작을 때는 모든 숫자를 하나하나 확인하는 것보다 훨씬 효율적으로 특정 범위 안에 존재하는 배수들의 합집합 크기를 구할 수 있다.

결국 핵심은 다음과 같다.

홀수 개의 집합이 겹치는 부분은 더하고
짝수 개의 집합이 겹치는 부분은 뺀다.

그리고 배수 집합의 교집합은 선택된 숫자들의 최소공배수의 배수 집합이라는 점을 이용하면 포함 배제의 원리를 그대로 코드로 옮길 수 있다.