문제 :

첫번째 층의 노드 개수가 n개이고 이를 각각 a1, a2, ... an라고 합시다. 마지막 층의 노드 개수는 m개이며 m>=n입니다. 마지막 층에서 n개를 골라서 각각을 dst(a1), dst(a2), ... dst(an)로 정합니다. 그리고 a1 to dst(a1), a2 to dst(a2), ... an to dst(an) 을 이루는 경로들 중 하나를 골라서 각각 path(a1), path(a2), ... path(an)라고 합시다. 이때 각각의 path들은 모두 서로 다른 노드들로만 이뤄져야 합니다 (어떤 path 자신에 포함되는 노드는 다른 어떤 path에도 포함되지 않음.). 그러면 이들 path의 비용 총합이 최소가 되게 하는 어떤 하나의 path조합을 구하는 방법은 무엇입니까? 또한 층의 개수를 k개라고 할 때, 이 문제를 최악의 경우에 가장 빨리 푸는 알고리즘에 대해 n, m, k에 관한 최악시간 시간복잡도는 얼마입니까?.


문제 예시 :

첫번째 층의 노드 개수가 3개이고 이를 각각 A, B, C라고 합시다. 마지막 층의 노드 개수는 5개입니다. 마지막층에서 3개를 골라서 각각을 dst(A), dst(B), dst(C)로 정합니다. 그리고 A to dst(A), B to dst(B), C to dst(C)로 가는 경로들 중 하나를 골라서 각각 path(A), path(B), path(C)라고 합시다. 이때 path(A), path(B), path(C)는 모두 서로 다른 노드들로만 이뤄져야 합니다. 그러면 path(A), path(B), path(C)의 비용 총합을 최소화하도록 각각의 path를 선택하는 방법은 무엇입니까?