jh05013   4년 전

주은이와 명진이는 사적으로 위스키를 거래하는 사이이다. 주은이는 돈도 많고 위스키를 무척 좋아해서 위스키를 가능한 한 많이 사고 싶어하고, 명진이는 위스키가 넘쳐나서 위스키를 가능한 한 많이 팔고 싶다. 하지만 주은이 자신의 사회적 평판과 품위 때문에, 한 번에 너무 많은 양의 위스키를 직거래하는 것을 꺼려 한다. 그래서 주은이는 자신의 친구를 총동원하고 명진이에게도 은밀하게 부탁하여 사설 유통망을 구축해내기로 했다. 유통망의 구조는 다음과 같다.

  • 주은이가 명진이에게 위스키를 주문한다.
  • 명진이는 가능한 한 많은 위스키를 적절하게 분배하여 명진이의 친구들에게 발송한다.
  • 명진이의 친구들은 자신의 연락망을 토대로 유통망 안에서 위스키를 주고받을 수 있다. 이들 중 몇몇은 주은이의 친구들과 연락할 수 있지만, 주은이와 직접 연락할 수는 없다.
  • 명진이의 친구들에게서 위스키를 전달받은 주은이의 친구들은 모든 위스키를 주은이에게 전달한다.

명진이는 위스키를 무한하게 보낼 수 있고, 주은이 역시 친구들로부터 받을 수 있는 위스키의 양에 제한이 없다. 하지만 명진이와 주은이의 친구들도 각자의 사회적 평판을 걱정하기 때문에 각각 한 명에게서 전달받을 수 있는 양이 정해져 있다. 예를 들어 A가 한 번에 최대 5병의 위스키를 받을 수 있다면, A는 3명의 친구들로부터 위스키를 5병씩 전달받아서 주은이에게 총 15병을 전달할 수 있지만, 1명의 친구로부터 6병을 전달받지는 못한다.

각 친구들이 한 명에게서 최대 몇 병의 위스키를 전달받을 수 있는지, 명진이의 친구들이 누구에게 연락할 수 있는지에 대한 정보가 주어졌을 때, 주은이가 한 번에 최대 몇 병의 위스키를 받을 수 있을지를 구하여라.

startlink   4년 전

수정했습니다.

댓글을 작성하려면 로그인해야 합니다.