Cowpatibility( BOJ 16764 )

문제

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

16764번: Cowpatibility

 

문제 파악하기

• 친구가 될 수 없는 소들의 쌍을 찾는 문제입니다.
• 아이스크림의 맛은 총 5개 입력되며, 단순히 중첩 반복문을 사용하기에는 N의 값이 너무 큽니다.
• 단순히 아이스크림 맛을 카운트하기에는 중복되는 소들을 계산할 수 없습니다.
• 이 문제는 map 자료형을 사용해야 합니다.

 

문제 해결하기 #1

• map은 탐색에 필요한 키값과 해당 키값에 할당된 내용값으로 구성됩니다.
• 각 소마다 5가지의 맛을 좋아하므로 나올 수 있는 맛의 부분 집합 수는 총 31가지(공집합X) 입니다.
• 그렇다면 31가지 경우를 map에 저장한 다음, 각 경우의 수에 해당하는 소의 개수를 카운트하면 되지 않을까요?
• 예를 들어 1번 소는 {1, 2, 3, 4, 5}를 좋아하고 2번 소는 {2, 3, 4, 10, 6}을 좋아한다고 가정해봅시다.
  그렇다면 1번 소와 친구가 될 수 있는 경우의 수는 {1}, {2}, ... , {1, 2, 3, 4, 5}까지 총 31가지가 됩니다.
  또한 2번 소와 친구가 될 수 있는 경우의 수는 {2}, {3}, ... , {2, 3, 4, 10, 6}까지 총 31가지 있습니다.
  여기서 1번 소와 2번 소가 친구가 될 수 있는 경우의 수는 중복을 제외하면 1가지가 나오게 됩니다.
• 이렇듯 map에는 vector형을 이용한 부분집합을 키값으로 하고, 해당 경웨 해당하는 소의 개수를 내용값으로 할당합니다.
• 그 후, 각각의 부분집합에 대해 포함된 소의 개수를 포함-배제 기법을 통해 카운트하면 문제를 풀 수 있습니다.

 

문제 해결하기 #2

• bitset이라는 자료구조를 사용하는 방법도 있습니다.
• bitset은 원하는 크기의 비트값을 저장할 수 있는 자료형입니다.
• 각각의 맛을 어떤 소가 좋아하는지 비트값으로 저장하면 손쉽게 겹치는 소의 마리수를 파악할 수 있습니다.
• 예시)  map< int, bitset<50000> > m;
• 위와 같이 map을 선언하면 해당 맛을 좋아하는지 여부에 따라 1 또는 0의 비트열을 저장합니다.
• 이후에는 각각의 소가 좋아하는 맛을 입력받을 때마다 OR연산을 진행하면 됩니다.
  5가지 맛을 모두 입력받았으면 m.count()를 이용해 1의 개수(소의 마리수)를 카운트하면 됩니다.
• 마지막으로 지금까지 카운트된 소의 마리수를 전체 경우의 수( n*(n-1)/2 )에서 빼주면 문제는 해결됩니다.

 

후기

map을 떠올리지 못해 고생했던 문제입니다. 개인적으로 bitset을 이용한 풀이법이 간편했는데 공식 솔루션을 확인해보니 포함_배제를 염두한 문제였다는게 새로웠습니다.