[BAE/<JOON>] 1516. 게임 개발

www.acmicpc.net/problem/1516

1516번: 게임 개발

풀이 ||

사실 위상정렬에 더 가까운 문제고 점화식은 딱히 없다. 그냥 메모이제이션만 하면 된다.

 

각각의 건물을 지을 때 필요한 선행 건물들을 인접 리스트 방식으로 저장하고

 

TOP-DOWN방식으로 각 건물을 짓는데 걸리는 시간을 계산한다.

 

한가지 주의할 점은 건물 여러개를 동시에 지을 수 있기 때문에 

 

이러한 형태처럼 한 건물을 짓는데 2개 이상의 선행 건물이 필요할 경우에는 

 

걸리는 시간이 가장 긴 루트 하나만 선택하면 된다.

 

점화식 ||

각각의 건물을 짓는 최소 시간을 메모이제이션한다.

 

코드 ||

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> arr;
vector<int> val;
vector<int> dp;
int n;

int r(int np) {
	int& ret = dp[np];
	if (ret != -1) return ret;
	if (arr[np].size() == 0) return ret = val[np];
	int max = -1;
	for (auto v : arr[np]) {
		int s1 = r(v);
		max = max > s1 ? max : s1;//값이 여러개라면 가장 오래걸리는 루트로 계산
	}
	return ret = max + val[np];//최솟값 메모이제이션
}

int main()
{
	cin >> n;
	val = vector<int>(n + 1);
	arr = vector<vector<int>>(n + 1);
	dp = vector<int>(n + 1, -1);

	for (int i = 1; i <= n; i++) {
		int v;
		cin >> v;
		val[i] = v;
		int a;
		do {
			cin >> a;
			if (a == -1) break;
			arr[i].push_back(a);
		} while (a != -1);
	}

	for (int i = 1; i <= n; i++) {
		cout << r(i) << "\n";
	}

	return 0;
}