2637. 장난감 조립

오랜만?

2637번: 장난감 조립

---

부품을 계속 조립해서 완제품을 만드는데, 완제품을 만들기 위해 필요한 기본 부품의 수를 구하는 문제이다.

 

문제를 잘 읽고 다음의 내용을 생각할 수 있어야 한다. 못 했다고? 그럼 다음부터 하면 되지.

기본 부품이란 무엇인가?

기본 부품이란 다른 부품에 의해 제작되지 않는 부품이다. 어렵게 말하면 다른 부품에 의존성이 없는 부품이고, 쉽게 말하면 입력에서 $x$로 등장한 적이 없는 부품이다.

어떻게 계산할까?

사실 어떻게 계산할까보다 어떻게 나타낼까가 더 중요하다. 부품의 수가 최대 100개로 많지 않으므로 간단하게 배열로 나타내자. 정리하면 다음과 같다.

어떤 부품을 만들기 위해 필요한 기본 부품의 수를 배열로 나타내자.

$i$번 부품을 만들기 위해 필요한 기본 부품의 수를 $require[i]$로 나타내자. $1 \le i \le N$에 대해 $require[i]=\sum{require[c]*count}$이다. 이때 $c$와 $count$는 각각 부품 $i$를 만들기 위해 필요한 부품의 번호와 개수이다. 같은 값이 여러 번 필요할 수 있으므로 메모이제이션까지 적용하자.

 

이제 $require[N]$을 구하여 출력하기만 하면 된다.

---

 

난이도에 비해 티어가 너무 높아서 이유를 찾아봤더니 위상 정렬이 필요하다네? 굳이 위상 정렬을 할 필요가 없다. 위에서 푼 것처럼 재귀 dp면 충분하다.