[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

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 14897번: 서로 다른 수와 쿼리 1  (0) 2019.09.08
[BOJ] 17373번: 녜힁  (0) 2019.09.07
[BOJ] 16765번: Teamwork  (0) 2019.08.09
[BOJ] 16763번: Fine Dining  (0) 2019.08.08
[BOJ] 1099번: 알 수 없는 문장  (0) 2019.08.01
[BOJ] 10711번: 모래성  (2) 2019.07.23
  Comments