[백준] 2637 - 장난감 조립

https://www.acmicpc.net/problem/2637

2637번: 장난감 조립

 

dfs + dp 문제이다.

 

먼저 기본 부품을 구하는 과정은 위상 정렬을 하기 위해 사용하는 입력 간선 배열로 구하였다.

입력 간선의 개수가 0이면, 기본 부품이라는 뜻이다.

 

답을 구하는 과정은 임의의 부품의 번호 정점부터 완제품까지의 경로의 가중치의 곱이다.

따라서 dp[i] = 완제품을 만들기 위해 필요한 i 부품의 개수 로 정의하였다.

 

여기서 주의해야 할 점은 dfs 중에 완제품 까지 도달했을 때, 곱을 해야 하기 때문에 0이 아닌 1을 반환해야 한다는 점이다.

 

#include <iostream>
#include <vector>
using namespace std;

int n, m;
vector<vector<pair<int, int>>> v;
int inp[101], dp[101];

int get(int node, int pre) {

	if (dp[node]) return dp[node];
	if (node == n) return 1;

	int ret = 0;
	for (auto& i : v[node]) {
		if (i.first != pre) {
			ret += i.second * get(i.first, node);
		}
	}

	return dp[node] = ret;
}

int main() {

	cin >> n >> m;
	v.resize(n + 1);
	
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[b].push_back({ a,c });
		inp[a]++;
	}

	for (int i = 1; i <= n; i++) {
		if (inp[i] == 0) {
			cout << i << ' ' << get(i, 0) << '\n';
		}
	}
}