[BAE/<JOON> 문제풀이] 2637. 장난감 조립

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

2637번: 장난감 조립

핵심::
DP문제이긴 하지만 점화식 보다는 메모이제이션으로 중복 탐색 제거가 포인트

풀이::
DP[대상부품번호][필요부품번호] = 필요한 개수

우선 기본 부품은 진입 간선 수를 보고 미리 파악해둔다.

이 후, 탑-다운 방식으로 완제품에 필요한 부품에서 기본 부품으로 내려가며 필요한 부품 수를 파악한다.

단, 아래로 내려가면 중복 계산이 발생 할 수 있으므로 DP 배열에 자기 번호를 탐색된 부품인지로 보며 이미 탐색된 부품은 탐색하지 않는다.

의견::
사실 필요 부품 수만큼 곱하는 로직을 제외하면 그냥 피보나치 수열 문젠데 골드 2는 너무 높다.

13302 골4가 훨씬 어려웠음

 

코드::

// 2637
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

struct p {
	int n, c;
};

int n, m;
vector<vector<p>> arr;
vector<vector<int>> dp;
vector<int> ic;

vector<int> getp(int cn) {
	auto& ret = dp[cn];
	if (ret[cn] == 1) return ret;	
	ret[cn] = 1;
	for (auto val : arr[cn]) {
		auto pc = getp(val.n);
		for (int i = 1; i <= n; i++) {
			ret[i] += pc[i] * val.c;
		}
	}
	return ret;
}

int main()
{
	cin >> n >> m;
	ic = vector<int>(n + 1, 0);
	arr = vector<vector<p>>(n + 1);
	dp = vector<vector<int>>(n + 1);
	for (int i = 1; i <= m; i++) {
		int c, t, cnt; cin >> c >> t >> cnt;
		arr[c].push_back({ t, cnt });
		ic[c]++;
	}

	vector<int> bp;

	for (int i = 1; i <= n; i++) {		
		dp[i] = vector<int>(n + 1);
		if (ic[i] == 0) {
			bp.push_back(i);
			dp[i][i] = 1;
		}
	}	

	auto ret = getp(n);

	for (auto b : bp) {
		cout << b << " " << dp[n][b] << "\n";
	}

	return 0;
}