백준1516 게임개발 - C++

건물의 종류와 짓는 시간이 주어지고,

각 건물은 먼저 특정 건물이 지어지고 난 이후에나 지을 수 있다.

 

모든 건물 N개를 완성하는데 걸리는 최소 시간을 출력하면 되므로

일단 DP를 염두에 둘 수 있다.

명령을 내리고 일꾼이 이동하는 시간은 걸리지 않으므로

건물을 짓는 시간만 계산할 수 있고 

건물마다 번호가 있으므로 간편하게 DP로 저장할 수 있을 것으로 기대한다.

 

여기서 두 번째 조건이 걸린다.

특정 건물이 지어지고 난 이후에나 지을 수 있는 건물들이 있는데,

여기서 문제에 나오지 않았지만,

여러 개의 건물이 필요한 경우가 있을 수도 있으므로 

이런 경우에도 통과할 수 있도록 indegree를 센다.

indegree는 자신에게 들어오는 경로의 개수를 의미하는데,

1, 2 번이 지어지고 난 이후 3번을 지을 수 있다면

1, 2 → 3 의 순서로 생각할 수 있고,

3번 입장에서는 1,2에서 경로가 들어오는 것이므로 

indegree = 2 로 볼 수 있다.

 

모든 건물이 지어지는 것이 가능한 경우만 주어지므로

특정 건물 순서에 순환은 없다고 생각할 수 있으므로

위상 정렬 Topoligical Sort의 개념을 섞어서 생각할 수 있다.

 

즉, 위상정렬처럼 Indegree 가 0 인 건물부터

(조건을 만족해 건물을 지을 수 있는 경우부터)

짓기 시작하고, 그 때 걸리는 시간은 dp배열에 저장한다.

 

그런데 생각해보면 DP가 굳이 필요할까?

건물을 지을 때 순서는 항상 강제된다.

가령 1 → 2 → 3 순서로 지어야 하고 동시에

4 → 5 → 2 순서로 지어야 한다고 해보자.

그러면 그래프는 아래와 같을 것이다.

       1 → 2 → 3

4 → 5 ↗

그러면 2번은 어떻게 해도

1번을 짓는 시간 vs 4번을 짓고 5번을 짓는 시간

중 더 큰 쪽 시간 다음에나 지을 수 있다.

고로 DP[2] 에는 DP [1] + 1번 짓는 시간이나

DP[5] + 5번 짓는 시간 (DP [5] = DP [4] + 4번 짓는 시간)

중 큰 값이 들어가므로 DP[2] = MAX(DP [2], DP [1] + A [1]) OR MAX(DP [2], DP [5] + A [5])이다.

 

더 큰 값을 저장하는데 최소 시간을 구할 수 있을까?

그렇다.

왜냐하면 여기서 최소 시간은 같이 지을 수 있는 건물을

최대한 많이 같이 지음으로써 위의 경우와 같이

항상 보장되기 때문이다.

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


struct build
{
	vector<int> pre; //선행빌드의 번호, 빌드까지 시간
	int time;
	int indegree;
	build()
	{
		indegree = 0;
		time = 0;
	}
};
int N, a;
build A[501];
int dp[501];
queue<int> q;

int main()
{
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		int j = 0;
		while (1)
		{

			cin >> a;
			if (a == -1) break;
			if (j == 0) {
				A[i].time = a;
				dp[i] = a;
				j++;
			}
			else
			{
				A[a].pre.push_back(i);
				A[i].indegree++;
			}

		}
	}
	for (int i = 1; i <= N; i++)
	{
		if (A[i].indegree == 0)
			q.push(i);
	}
	while (!q.empty())
	{
		int node = q.front();
		q.pop();
		for (int i = 0; i < A[node].pre.size(); i++)
		{
			int nextnode = A[node].pre[i];
			dp[nextnode] = max(dp[nextnode], A[nextnode].time + dp[node]);
			A[nextnode].indegree -= 1;
			if (A[nextnode].indegree == 0) q.push(nextnode);
		}
	}
	for (int i = 1; i <= N; i++)
	{
		cout << dp[i] << endl;
	}
	
}