매년 크리스마스가 되면 부모들은 아이들이 만족할 수 있도록 크리스마스 선물을 주기 위해 고민을 하게 된다. 특히 아이들은 다른 아이가 받은 선물을 보고 부러워할 수 있기 때문에, 남을 부러워하는 아이가 없도록 선물을 잘 선택해야 한다.

올해도 어김없이 크리스마스가 왔기 때문에, 상수는 올해에도 까다로운 아이들에게 선물을 줘야 한다. 선물을 사러 가기 전에 상수는 아이들에게 선물 리스트를 보여준 뒤, 각 아이들에게 원하는 선물을 물어봤다. 아이들이 선물을 고르기만 하면 좋겠지만, 남이 가진 선물이 나한테 없다면 슬픈 아이들이 있을 것이라는 것 정도는 충분히 유추할 수 있을 것이다.

까다로운 조사 끝에, 상수는 아이들의 요구들을 4가지 종류로 나눴다.

종류 1. 선물 집합

종류 2. 특정 아이가 가지고 있는 선물 전체

종류 3. 종류 1 또는 종류 2에 해당하는 조건 2개의 “교집합”

종류 4. 특정 아이가 가지고 있는 선물 중, 특정 몇 가지를 제외한 것

각 아이는 여러 가지의 요구를 동시에 할 수 있으며, 이 때 모든 요구 조건이 만족되어야 아이가 불평하지 않는다. 이 때 선물을 최소한으로 구매하여 모든 아이의 요구 조건을 만족시키는 선물 구매 목록을 출력하여라.

예를 들어, 세 아이 (정올, 수올, 물올)와 선물 (정보, 수학, 물리)에 대해서, 각 아이가 다음과 같은 요구를 했다고 하자.

정올은 {정보, 수학}과, {수올}과 {물올}이 가진 선물의 교집합을 원한다.
수올은 {물올이 가진 선물}과 {수학, 물리}의 교집합을 원한다.
물올은 {정보}와, {정올이 가진 선물}에서 {물리}를 뺀 것을 원한다.

정올에게 {정보, 수학}을, 수올에게 {수학}을, 물올에게 {정보, 수학}을 사주는 것이 최소이다.

#3550 upload 12 done 4 how_to_reg 4

크리스마스 선물 timer 3s memory 128MB

#3550

크리스마스 선물 3s 128MB