백준 1005 ACM Craft (c++) : 피너클

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

1005번: ACM Craft

다이나믹 문제다.

1년전에 풀어져있어 코드를 봤는데 위상정렬 없이도 풀어져있었다.

int n, k, w;
long long delay[1001];
bool firstBuild[1001];
vector<int> v[1001];
int cache[1001];

사용할 변수다.

delay[5] = 5라면 5번 건물을 지을때 5만큼 시간이 든다는 것이다.

firstBuild[5] = true라면 5번 건물은 바로 지을수 있는 건물이란 것이다.

int test;
cin >> test;
while (test-- > 0) {

메인함수에선 test를 입력받고 while문을 돌리며 시작한다.

    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> delay[i + 1];
    for (int i = 0; i < n; i++) firstBuild[i + 1] = true;
    for (int i = 0; i < n; i++) cache[i + 1] = -1;
    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        v[b].push_back(a);
        firstBuild[b] = false;
    }
    cin >> w;

값들을 입력받으며 배열들을 초기화한다.

firstBuild는 처음에는 전부 true로 했다가 a와 b를 입력받을때 b건물은 false로 바꾼다.

cache도 전부 -1로 초기화하고

v[b]에 a를 넣는다. b건물을 짓기위해 필요한 건물이 v[b]에 들어있다.

그후 w를 입력받는다.

    long long result = solve(w);

    for (int i = 1; i <= n; i++) v[i].clear();

    cout << result << endl;
}

그후 result에 solve(w)를 집어넣고 v를 초기화한뒤 result를 출력하면 된다.

long long solve(int b) {
	if (firstBuild[b]) return delay[b];
	if (cache[b] != -1) return cache[b];

solve함수다.

만약 b건물이 바로 지을수 있는 건물이면 delay[b]를 반환하고

만약 b건물이 이전에 지어본적 있다면 cache[b]를 반환한다.

	long long result = delay[b];
	long long plus = 0;

result는 b건물을 짓는데 걸리는 시간이고 plus는 b건물을 짓기 위해 필요한 건물들을 짓는데 걸리는 시간이다.

	for (int i = 0; i < v[b].size(); i++) {
		plus = max(plus, solve(v[b][i]));
	}

그후 v[b]의 사이즈만큼 반복을 돌리며 plus에 max(plus, solve(v[b][i])를 넣는다.

max를 하는 이유는 

위 상황에서 3건물을 짓는데 1, 2건물이 필요하고 1 건물을 짓을때는 10시간이 걸리고 2건물을 지을때는 30시간이 걸린다.

max가 아닌 min으로 할경우 plus에는 10이 들어갈것이다. 하지만 아무리 건물짓기를 동시에 진행한다해도

10시간 안에는 1건물과 2건물 둘다 짓지 못한다. 3건물을 짓는데는 1, 2건물이 필요하지만 말이다.

그렇기 때문에 max로 하는 것이다. 3건물을 짓기 위해 필요한 건물중 가장 많은 시간이 걸리는 건물을 plus에 넣는것이다.

	return cache[b] =  result + plus;
}

마지막으로 result + plus를 cache[b]에 넣으며 반환한다.

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

using namespace std;

int n, k, w;
long long delay[1001];
bool firstBuild[1001];
vector<int> v[1001];
int cache[1001];

long long solve(int b) {
	if (firstBuild[b]) return delay[b];
	if (cache[b] != -1) return cache[b];

	long long result = delay[b];
	long long plus = 0;

	for (int i = 0; i < v[b].size(); i++) {
		plus = max(plus, solve(v[b][i]));
	}

	return cache[b] =  result + plus;
}

int main(){
	int test;
	cin >> test;
	while (test-- > 0) {
		cin >> n >> k;
		for (int i = 0; i < n; i++) cin >> delay[i + 1];
		for (int i = 0; i < n; i++) firstBuild[i + 1] = true;
		for (int i = 0; i < n; i++) cache[i + 1] = -1;
		for (int i = 0; i < k; i++) {
			int a, b;
			cin >> a >> b;
			v[b].push_back(a);
			firstBuild[b] = false;
		}
		cin >> w;

		long long result = solve(w);

		for (int i = 1; i <= n; i++) v[i].clear();

		cout << result << endl;
	}
}

전체코드다.