문제 설명:

A B C D.. 이런식으로 이벤트들이 주어지고

이벤트마다

1. 참여한 유저와 상품수가 정해져있고,

2. 참여한 유저 수>= 상품수인게 보장되어 있음

(각 유저는 1개 이상의 이벤트에 참여함)

이 이벤트 세트에는 한 가지 제약이 있음 .

앞선 이벤트에서 상품을 받으면 다음 이벤트에선 추첨 대상자에서 제외된다는 거임

뭔소리냐? 예를 들면 치킨이벤트에 성공했음 버거 추첨에선 제외하는? 그런거임

이때 문제 상황이 발생할 수 있는데 추첨 가능 인원수가 줄어들면서

이벤트 상품 숫자 < 추첨 가능 인원 숫자인 경우가 발생해 추첨을 진행할 수 없는 상황이  발생할 수 있음




예를 들면 이벤트 C에 참여자 a b c가 있고 여기저 피자를 두명 주는데

앞선 이벤트에 a b가 치킨을 받았으면 한 명만 남았는데 경품이 둘이라 해당 이벤트가 성립하지 않음



이때 추첨의 진행 과정에 따라

이벤트 중 하나라도 성립하지 않을 가능성이 있는지 True/False를 판별해보고 싶음







잡소리:


이벤트를 직 이벤트 세트가 성립하지 않을 가능성이 있는지 미리 판단하는 코드를 짜봤었음

이 문제에 대해 컴비네이션이랑 DFS 이용해서 모든 경우의 수를 탐색하는 방식으로 풀었는데

실제로 22명 중 7명 고르는게 포함된 걸 실행시켜보니 시간이 꽤 오래걸렸음

11C2 x 22C7 을 시킨 나의 잘못이 크긴해

그래서 DFS같은 원시적 방법말고 더 좋은 솔루션이 있을까 생각해보고 있는중..