BOJ 16764 - Cowpatibility (포함배제, 부분집합)

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

 

<문제설명, 풀이>

https://acm-iupc.tistory.com/8

 

<풀이+>

i번째 소에 대한 정보가 들어올 때, 1번~i-1번소 중 i번 소와 compatible한 쌍의 개수를 세준다.

 

어디서? 부분집합을 만드는 코드에서

 

이때, 포함배제를 사용할 부분은 1~i-1번 소이기때문에 mp[v]는 나중에 ++해준다.

 

<코드>

ll n, a[5], r;
map<vector<ll>, ll> mp;

int main() {
	cin >> n;
	for (int j = 0; j < n; j++) {
		for (int i = 0; i < 5; i++) cin >> a[i];
		sort(a, a + 5);

		for (int x = 1; x < (1 << 5); x++) {
			vector<ll> v;
			for (int i = 0; i < 5; i++)
				if (x & (1 << i)) v.push_back(a[i]);

			r += (v.size() % 2 ? 1 : -1) * mp[v];
			mp[v]++;
		}
	}
	cout << n * (n - 1) / 2 - r << '\n';
}

 

<생각>

공식 솔루션에선 포함배제를 할 때 집합 크기가 아닌 집합크기C2를 하던데, 어떻게 그게 가능한진 모르겠다;;