05. 조합 탐색 - 예제2

[1. 문제 설명]

m가지의 음식을 준비할 수 있고, n명의 친구를 초대하려고 한다.

각 친구가 먹을 수 있는 음식, 먹을 수 없는 음식이 주어질 때,

각 친구가 먹을 수 있는 음식이 최소한 하나씩 있게 하려면 

최소 몇가지의 음식을 해야하는가?

---

[2. 풀이 접근]

NP 완비 문제 중 하나로, 다항 시간에 푸는 방법은 아직 없다.

 

탐욕적 접근 방법으로 가장 많은 사람들이 먹을 수 있는 음식을 만들어 보는 방식으로 접근 할 수 있지만,

모든 입력에 대해 최적해를 찾아낼 수는 없다.

예제) ???

 

완전 탐색으로 접근 해서, 간단한 가지치기를 하면 답을 구할 수 는 있지만,

시간 내에 동작하지 않는다.

 

이 문제를 푸는 간단한 방법은 탐색의 형태를 바꾸는 것 이다.

매 재귀 호출마다 아직 먹을 음식이 없는 친구를 하나 찾은 뒤, 이 친구를 위해 어떤 음식을 만들지 결정 하는 것이다.

 

 

탐색의 방향을 바꿨을 때, 별다른 최적화 없이 더 빠른 이유는

• 항상 모든 친구가 먹을 음식이 있는 조합만을 찾는다.
• 매 호출마다, 항상 음식을 하나 하게 된다.
• 불 필요한 음식을 하는 경우가 없다.

 

아래 방법을 이용하면 더 최적화 할 수 있다.

• 먹을 수 있는 음식의 종류가 적은 친구를 찾도록 한다.
  => 
• 가장 많은 사람이 먹을 수 있는 음식부터 시도한다.
  => 

---

[3. 코드]