[BOJ] 16764번: Cowpatibility

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

 

예를 들어 어느 한 소가 선호하는 맛이 (1, 2, 3, 4, 5)라고 할 때

(1) (2) (3) (4) (5)

(1 2) (1 3) (1 4) (1 5) (2 3) ...

(1 2 3) (1 2 4) (1 2 5) (1 3 4) ...

(1 2 3 4) (1 2 3 5) ...

(1 2 3 4 5)

를 모두 저장합니다. map을 이용해도 되고 그냥 리스트에 넣어둔 후 정렬을 해두어도 됩니다.

 

이후 포함과 배제를 이용해, 나와 겹치지 않는 소의 수는

 

N - 맛 1개가 겹치는 소의 수 + 2개가 겹치는 소의 수 - 3개가 겹치는 소의 수 + 4개가 겹치는 소의 수 - 5개가 겹치는 소의 수이고 이를 이분탐색으로 빠르게 알아내면 됩니다.

 

https://github.com/blisstoner/BOJ/blob/master/16764.cpp