골드3 - 백준 1005 ACM Craft

백준 1005 ACM Craft

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

접근방법

목표 건물을 짓기 위해서는 선행되어 지어져야하는 건물이 있다. 하지만 선행건물이 전부 지어지는데 걸리는 시간은 선행건물들 중 가장 늦게 지어지는 건물이 지어지면 그 전에 다른 모든 건물들이 지어지므로, 가장 늦은 시간만 생각해주면 된다.
건물들이 지어지기 위해서는 연쇄적으로 차례차례 지어져야하므로 재귀를 이용했고, 어떠한 건물을 짓는데 선행건물까지 포함하여 짓는데 걸리는 시간을 저장하여 추후에도 참조할 수 있도록 했다.

풀이

preBuild의 이차원 백터에 어떠한 건물을 짓기 위해 선행으로 지어져야하는 건물들을 저장했고, preBuild[node]의 size를 이용해 선행 조건이 없는 건물들을 찾아서 dp배열을 초기화 해주었다.
목표 건물을 재귀함수에 입력해서 선행 건물들 중 최대 시간을 찾아서 현재 건물 짓는 시간을 더해주어 답을 출력해주었다. dp배열에 걸리는 시간이 저장되어 있지 않다면 재귀로 차례차례 값을 구해주었다.

코드

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

vector<vector<int>> preBuild;
int cost[1001];
int dp[1001];

int dfs(int node)
{
	if (dp[node] != -1)
		return dp[node];

	int Max = 0;
	for (int i = 0; i < preBuild[node].size(); i++)
	{
		int temp = dfs(preBuild[node][i]);
		if (Max < temp)
			Max = temp;
	}

	return dp[node] = Max + cost[node];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int T;
	cin >> T;

	while (T--)
	{
		preBuild.clear();
		memset(cost, 0, sizeof(cost));
		memset(dp, -1, sizeof(dp));

		int N, K;
		cin >> N >> K;

		for (int i = 1; i <= N; i++)
		{
			cin >> cost[i];
			vector<int> temp;
			preBuild.push_back(temp);
			if (i == 1)
				preBuild.push_back(temp);
		}

		for (int i = 0; i < K; i++)
		{
			int a, b;
			cin >> a >> b;
			preBuild[b].push_back(a);
		}

		for (int i = 1; i <= N; i++)
		{
			if (preBuild[i].size() == 0)
				dp[i] = cost[i];
		}

		int target;
		cin >> target;

		cout << dfs(target) << '\n';
	}

	return 0;
}