2637 장난감 조립 {boj}

풀이

흐름

1. 기본부품을 파악한다 -- indegree == 0인 노드들을 찾아서

2. 위상정렬을 수행한 결과를 거꾸로 (완제품부터 차례로) 다음 점화식을 따라 배열을 수정해간다

   topo = topological_sort(graph)
   needs = reverse direction of graph, which can query dependencies
   dp = [0, 0 ... 1]
   for composite_part in reversed(topo):
       for small_part, weight in needs[composite_part]:
           dp[small_part] += weight * dp[composite_part]