[백준/BOJ] 백준 16764번 : Cowpatibility

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

16764번: Cowpatibility

 

map<int, bitset<50005>> flavor에 "[맛] = 해당 맛을 어떤 소가 좋아하는지 비트로 표현한 정보(ex 0번 소랑 3번 소가 좋아할 때 01001)" 를 저장해 놓고, 소를 하나씩 확인하며 해당 소가 좋아하는 맛의 flavor에 값을 추가해 나아가면서, 이전에 확인한 소들 중에서 같은 아이스크림을 좋아하는 소가 있었는지 확인하고, 지금 확인하는 소와 짝이 되는 소들을 비트로 표시하여 짝의 개수를 구하고 난 뒤, 모든 소들을 확인하고 나서 전체 짝의 경우의 수에서 지금까지 구한 짝의 개수를 빼는 방법으로 문제를 해결했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <bitset>
using namespace std;

long long n;

//[맛] = 해당 맛을 어떤 소가 좋아하는지 비트로 표현 (ex 0번 소랑 3번 소가 좋아할때 01001)
//배열이 아닌 map으로 해서 메모리 줄이기 (최대 나올 수 있는 맛의 수가 250000 (50000*5)개 뿐이므로)
map<int, bitset<50005>> flavor;

long long pair_cnt = 0;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++) {

		bitset<50005> this_cow(0);
		this_cow.set(i); //i번째 소를 나타내는 비트

		bitset<50005> pair_cow(0); //i번째 소랑 짝이 되는 소들을 비트로 표현
		for (int j = 0; j < 5; j++) {
			int input;
			cin >> input; //i번 소가 좋아하는 맛

			if (flavor.count(input) == 0) { //처음 나오는 맛일때
				flavor.insert(make_pair(input, this_cow));
			}

			else { //이전에 나왔던 맛일때
				pair_cow = pair_cow | flavor[input]; //해당 맛을 좋아하는 이전에 나온 소들은 i번째 소랑 짝이 된다
				flavor[input] = (flavor[input] | this_cow);
			}
		}

		//i번째 소랑 짝이 되는 소들의 개수를 더한다
		pair_cnt += pair_cow.count();
	}

	cout << ((n * (n - 1)) / 2) - pair_cnt << "\n"; //전체 짝의 경우의 수 에서 짝의 개수를 뺀다

	return 0;
}