[BOJ/1516] 게임 개발, c++

www.acmicpc.net/problem/1516

1516번: 게임 개발

한줄 후기 : solved ac class 5를 따기 위한 눈물 겨운 여정..

---

 

문제를 읽으면서 건물 짓는 순서가 주어지길래 위상정렬인 것 같다고 생각하고 풀었다.

 

//AC
//BOJ 1516 게임 개발
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int ind[501];
int ans[501];
int c[501];
vector<int> v[501];
void topo(int N){
	queue<int> q;
	for(int i=1; i<=N; i++){
		if(ind[i] == 0){
			q.push(i);
		}
	}
	while(!q.empty()){
		int x = q.front();
		c[x] = ans[x];
		q.pop();
		for(int y : v[x]){
			ind[y] -= 1;
			ans[y] = max(ans[y], c[y]+ans[x]);
			if(ind[y] == 0){
				q.push(y);
			}
			
		}
	}
}
int main(){
	int N, t;
	cin >> N;
	for(int i=1; i<=N; i++){
		scanf("%d", &c[i]);
		ans[i] = c[i];
		while(1){
			scanf("%d", &t);
			if(t==-1)	break;
			v[t].push_back(i);
			ind[i]++;
		}
	}
	topo(N);
	for(int i=1; i<=N; i++){
		printf("%d\n", ans[i]);
	}	
	return 0;
}

그냥 풀면 틀린다. 아래는 처음 틀린 코드 

//WA
//BOJ 1516 게임 개발
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int ind[501];
int ans[501];
int c[501];
vector<int> v[501];
void topo(int N){
	queue<int> q;
	for(int i=1; i<=N; i++){
		if(ind[i] == 0){
			q.push(i);
		}
	}
	while(!q.empty()){
		int x = q.front();
		q.pop();
		for(int y : v[x]){
			ind[y] -= 1;
			if(ind[y] == 0){
				q.push(y);
				ans[y] += ans[x];
			}
		}
	}
}
int main(){
	int N, t;
	cin >> N;
	for(int i=1; i<=N; i++){
		scanf("%d", &c[i]);
		ans[i] += c[i];
		while(1){
			scanf("%d", &t);
			if(t==-1)	break;
			v[t].push_back(i);
			ind[i]++;
		}
	}
	topo(N);
	for(int i=1; i<=N; i++){
		printf("%d\n", ans[i]);
	}	
	return 0;
}

여러곳에서 건물을 모두 지어야만 지을 수 있는 건물들을 고려하지 않았었다.

그런 건물들은 전에 지은 건물들 중 최대 비용을 찾아줘야한다.

ans[y] = max(ans[y], c[y]+ans[x]);

그래서 이 부분이 키포인트이다.

매 건물마다 현재 건물 건설 비용+바로 직전 건물 건설 비용, 현재 비용(직전에 여러개를 지을 수 있으므로)

중 최댓값을 저장해주어야 한다.

아 비용이라 해서 왜 최댓값이지 라는 의문이 들 수 있는데 비용이 아니라 시간이니까 당연히 건물이 모두 지어질 때 까지 기다려야해서 최댓값으로 구해줘야한다.