백준 1005: ACM Craft

문제 요약

이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 있다. (동시에 진행이 가능하다) 그리고 4번 건물을 짓기 위해서는 2번과 3번 건물이 모두 건설 완료되어야지만 4번건물의 건설을 시작할수 있다.

따라서 4번건물의 건설을 완료하기 위해서는 우선 처음 1번 건물을 건설하는데 10초가 소요된다. 그리고 2번 건물과 3번 건물을 동시에 건설하기 시작하면 2번은 1초뒤에 건설이 완료되지만 아직 3번 건물이 완료되지 않았으므로 4번 건물을 건설할 수 없다. 3번 건물이 완성되고 나면 그때 4번 건물을 지을수 있으므로 4번 건물이 완성되기까지는 총 120초가 소요된다.

백준이를 위해 특정건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 프로그램을 작성해주자.

문제 분류

• 다이나믹 프로그래밍
• 그래프 이론
• 위상 정렬

문제 풀이

위상 정렬과 dp로 풀면 된다. ary[idx]는 idx번의 건물의 완성 시간이고, v[idx]는 이전 단계 건물의 번호를 vector로 넣은 것이다.
idx번의 건물의 완성 시간은 이전 단계의 건물 완성시간의 최댓값 + 대상 건물의 완성시간일 것이다. 이를 dp의 점화식으로 만들어서 풀어주었다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <memory.h>

using namespace std;

int n, k, ary[1000];
vector<int> v[1000];
long long dp[1000];

long long sol(int idx)
{
	long long temp = 0;
	if (v[idx].empty()) return ary[idx];
	if (dp[idx] > -1) return dp[idx];
	for (int i = 0; i < v[idx].size(); i++)
		temp = max(temp, sol(v[idx][i]));
	dp[idx] = temp + ary[idx];
	return dp[idx];
}

int main()
{
	int t, in1, in2, w;
	cin >> t;
	while (t--) {
		memset(dp, -1, sizeof(dp));
		scanf("%d%d", &n, &k);
		for (int i = 0; i < n; i++)
			v[i].clear();
		for (int i = 0; i < n; i++)
			scanf("%d", ary + i);
		
		for (int i = 0; i < k; i++) {
			scanf("%d%d", &in1, &in2);
			v[in2 - 1].push_back(in1 - 1);
		}
		scanf("%d", &w);
		printf("%lld\n", sol(w - 1));
	}
	return 0;
}