[백준 1516] 게임 개발

문제

백준 1516

유형

• 브루트포스

풀이

1043번과 거의 똑같이 풀이하였다. 선행되지 않아도 되는 건물이 무조건 있을 것이기 때문에 그런 건물들을 짓는 시간을 전부 저장해둔다.

1~N까지 계속 순회하면서 선행되어야하는 건물들을 짓는 시간의 최대값을 구한 후 해당 건물을 짓는 시간을 갱신해준다.

만약 아무것도 갱신되지 않으면 루프를 빠져나온다.

코드

#include <bits/stdc++.h>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;
int n;
int arr[501];
int original[501];
vector<int> v[501];

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x; cin >> x;
		arr[i] = x;
		original[i] = x;
		while (true) {
			cin >> x;
			if (x == -1) break;
			v[i].push_back(x);
		}
	}

	while (true) {
		bool c = false;
		for (int i = 1; i <= n; i++) {
			int M = 0;
			for (int j = 0; j < v[i].size(); j++) {
				M = max(M, arr[v[i][j]]);
			}
			if (arr[i] != original[i] + M) {
				c = true;
				arr[i] = original[i] + M;
			}
		}
		if (!c) break;
	}

	for (int i = 1; i <= n; i++) cout << arr[i] << '\n';

	return 0;
}