백준 14848

문제

풀이

그리디하게 풀 수 있을까 생각해서 시도했지만 풀지 못했다.

 

포함 배제 원리를 기반으로한 카운팅 방식으로 문제를 해결해야한다.

 

포함 배제의 원리

포함배제 원리란 각 집합의 합집합의 크기를 구하기 위해 사용되는 방법이다.

 

위키백과

Ai가 하나의 집합일때, A1 ~An의 합집합을 구하기 위해서는 겹치는 부분(교집합)을 빼줘야한다.

하지만 교집합을 빼주는 과정에서 중복된 부분이 생기고, 이 중복된 부분을 다시 체크해줘야 된다.

포함 배제의 원리는 집합의 개수가 홀수일때 전체 개수에 더해주고, 짝수일때 빼서 전체 합집합의 개수를 구하는 방법이다.

 

결국 [1, 2, 3, 4, 5]라는 입력이 들어왔을때 [1], [1,2], [1,3] ~~~ [1,2,3,4,5]와 같은 모든 집합의 조합의 경우의 수를 생각하고, 원소의 수에 따라 전체 개수를 카운팅해야 한다.

 

그렇다면 전체 개수를 어떻게 카운팅하면 좋을까

 

비트마스킹을 이용한 전체 조합의 경우 탐색

늘 하던것 처럼 백트래킹을 이용해서 조합의 경우의 수를 구하려 했는데 이렇게 된다면 각각의 leaf case에서 K만큼 배열을 탐색해 어떤 조합인지를 확인해야하므로 코스트가 많이 들게 된다.

 

풀이를 보니 비트마스킹을 통해 유연하게 조합의 개수를 구할 수 있다는 것을 알게되었다.

 

for(int i = 1; i<(1<<K); i++) {
        for(int j=0; j<K; j++) {
            if(i & (1<<j)) {
               // 조합에 j번째 수가 들어가는지.
            }
        }
    }

 

첫번째 반복문은 1를 K만큼 left shift한 값 까지 수행하는 반복문이다.

이는 K만큼의 비트수에 따른 모든 경우의 수를 탐색하는 경우, 각각의 비트에 들어갈 수 있는 경우의 수는 2다. (0, 1) 그러므로 2^K가지의 경우의 수가 생기게 된다. 

비트에 들어가는 모든 경우의 수를 다시 표현하면 각각의 원소들의 조합으로 표현할 수 있다. 그러므로 모든 조합의 경우를 탐색하기 위해 이렇게 표현하였다.

 

두번째 반목문은 0부터 K번 1를 leftshift 하여 특정 비트필드에 1이 있는지 확인하는 경우이다.

모든 경우의 수는 결국 bitmap size K로 되어있다. 그러므로 K만큼 왼쪽으로 shift하여 해당하는지 안하는지 확인한다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ull unsigned long long

ull N, K, chk[101], prime[101], ans, arr[16];
ull gcd(ull a, ull b) {
    if(b == 0) return a;
    else return gcd(b, a%b);
}
ull lcm(ull a, ull b) {
    return a*b/gcd(a, b);
}
int main() {
    cin>>N>>K;
    for(int i=0; i<K; i++) cin>>arr[i];
    sort(arr, arr+K);
    for(int i = 1; i<(1<<K); i++) {
        int cnt = 0;
        ull lcmnum = 1;
        for(int j=0; j<K; j++) {
            if(i & (1<<j)) {
                cnt += 1;
                lcmnum = lcm(lcmnum, arr[j]);
            }
        }
        if(cnt%2) ans += N/lcmnum;
        else ans -= N/lcmnum;
    }
    cout<<N-ans;
}