백준 1516 게임 개발 (c++) : 피너클

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

1516번: 게임 개발

다이나믹 문제다.

int n;
int cost[501];
int cache[501];
vector<int> v[501];

사용할 변수다.

cost[i]는 i건물을 지을때 드는 시간이다.

cache[i]는 i건물을 짓을때 드는 모든 건물의 시간이다.

i건물을 짓기위해 1번 건물도 지어야 한다면 1번건물 짓는 시간 + i건물 짓는 시간 이렇게 들어간다.

v[i] = [1, 2, 3]이라면 i건물을 짓기 위해서는 1, 2, 3 건물이 지어져 있어야 한다는 뜻이다.

cin >> n;
for (int i = 1; i <= n; i++) {
    int a;
    cin >> a;
    cost[i] = a;
    cache[i] = -1;

    while (true) {
        cin >> a;
        if (a == -1) break;
        v[i].push_back(a);
    }
}

for (int i = 1; i <= n; i++) {
    cout << solve(i) << '\n';
}

값을 입력받으며 cache를 -1로 초기화해준다.

그후 1부터 n까지 solve를 돌려주면 된다.

int solve(int idx) {
	if (v[idx].size() == 0) return cost[idx];
	int &ret = cache[idx];
	if (ret != -1) return ret;

solve함수다.

idx는 현재 짓는 건물의 번호다.

만약 v[idx]의 사이즈가 0이라면 idx건물을 짓기 위해서 다른 건물을 지을 필요가 없는 것이다. 바로 cost를 반환한다.

ret에 cache[idx]를 참조하고 만약 ret이 -1이 아니라면 그대로 반환한다.

	int ans = 0;
	for (int i = 0; i < v[idx].size(); i++) {
		ans = max(ans, solve(v[idx][i]));
	}
	return ret = ans + cost[idx];
}

그후 v[idx]안에 있는 모든 건물을 돌아보며 ans에 그중 가장 큰 solve를 넣는다.

3번 건물을 짓기위해 1번 건물과 2번 건물이 지어져야 하고

1번 건물을 짓는데 10의 시간이 들고 2번 건물을 지을때 30의 시간이 걸린다고 가정하자.

min으로 ans를 업데이트 한다면 당연히 ans에는 10이 들어간다. 하지만 10시간이 지나고도 2번 건물은 지어지지 않는다.

max로 ans를 업데이트 한다면 당연히 30이 들어가고 30시간이 지나면 모든 건물이 지어진다.

그렇기에 max로 ans를 업데이트하는 것이다.

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

using namespace std;

int n;
int cost[501];
int cache[501];
vector<int> v[501];

int solve(int idx) {
	if (v[idx].size() == 0) return cost[idx];
	int &ret = cache[idx];
	if (ret != -1) return ret;

	int ans = 0;
	for (int i = 0; i < v[idx].size(); i++) {
		ans = max(ans, solve(v[idx][i]));
	}
	return ret = ans + cost[idx];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;
		cost[i] = a;
		cache[i] = -1;

		while (true) {
			cin >> a;
			if (a == -1) break;
			v[i].push_back(a);
		}
	}

	for (int i = 1; i <= n; i++) {
		cout << solve(i) << '\n';
	}
}

전체코드다.