[BOJ] 백준 1005번: ACM Craft

문제 링크

1005번: ACM Craft

 

예제 그림.

예제 그림은 4번 건물을 짓기 위하여 2번과 3번 건물이 모두 지어져야 하고, 2번과 3번을 짓기 위하여 1번 건물이 지어져야 하는 경우를 보여준다.

이때 4번 건물을 짓기위해 걸리는 최소 시간은 1->3->4 를 짓는 시간인 120초가 걸리게 된다.

즉, i번 건물까지 짓는 시간은 자신의 상위 건물(j..) 들 중 가장 오래 걸리는 시간에 영향을 받는다.

동적 계획법을 사용하여 dp[i]를 i번째 것물을 짓는 최소 시간이라고 한다면 아래 식으로 정리할 수 있다.

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <memory.h>
#include <string>
#include <algorithm>
#define MAX_SIZE (1000001)
using namespace std;
typedef long long ll;

int n, k, w;
int cost[1001];
int dp[1001];
vector<int> v[1001];
int recv(int node) {
	int _size = v[node].size();
	if (!_size) { // 맨 먼저 지을 수 있는 건물
		return dp[node] = cost[node];
	}
	int& ret = dp[node];
	if (~ret) return ret;
	ret = 0;
	for (int j = 0; j < _size; j++) {
		ret = max(ret, recv(v[node][j])); // argmax j 
	}
	ret += cost[node];
	return ret;
}
void solve() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> cost[i];
		v[i].clear();
	}
	for (int i = 0; i < k; i++) { 
		int a, b;
		cin >> a >> b;
		v[b].push_back(a); //b를 짓기 위하여 a가 먼저 지어져야함.
	}
	cin >> w;
	memset(dp, -1, sizeof(dp));
	cout << recv(w) << "\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	for (; t--;) {
		solve();
	}
}