[BOJ] 1516번 게임 개발 (C++)

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

1516번: 게임 개발

 

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

int n;
int cost[501];
vector<int> edge[501];
int indegree[501];
int dp[501];

void topologicalSort(){
	queue<int> q;
	for(int i = 1; i <= n; i++){
		if(indegree[i] == 0){
			q.push(i);
			dp[i] = cost[i];
		}
	}
	
	while(!q.empty()){
		int c = q.front();
		q.pop();
		for(int i = 0; i < edge[c].size(); i++){
			int n = edge[c][i];
			if(--indegree[n] == 0){
				q.push(n);
			}
			dp[n] = max(dp[n], cost[n] + dp[c]);
		}
	}
}

int main() {
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> cost[i];
		int input;
		cin >> input;
		while(input != -1){
			indegree[i]++;
			edge[input].push_back(i);
			cin >> input;
		}
	}
	
	topologicalSort();
	
	for(int i = 1; i <= n; i++){
		cout << dp[i] << '\n';
	}
	return 0;
}

 

위상정렬 + dp 문제

 

특정 건물을 짓기 위해 걸리는 시간은,

해당 건물을 짓기 위해 우선적으로 지어야 하는 건물들 중 가장 오래 걸리는 시간 + 특정 건물을 짓기 위해 걸리는 시간