[백준] 1516-게임개발(C++)

문제링크:www.acmicpc.net/problem/1516

1516번: 게임 개발

 

문제를 보자마자 아이디어는 금방 떠올랐습니다.

 

문제조건에서 

• 편의상 자원은 무한히 많이 가지고 있고,
• 건물을 짓는 명령을 내리기까지는 시간이 걸리지 않는다

하였으니 단순히 이전 건물을 짓는데 시간과 자신의 건축시간을 더한 값입니다.

 

dp[num]을 자신의 건물 완성 최소시간이라 할때

dp[num] = 자신의 건축시간 + max(선이수 건물 완성 최소시간) 입니다.

 

 

이때 구현방법을 고민해봐야 합니다.

일반적인 dp구현방식인 (down-up) 방식을 사용할 수 없습니다. 선이수 건물이 이미 완성 되었는지 모르기 때문입니다.

즉, 재귀호출방식(up-down)방식을 사용해야합니다. 이때 이미 구한 값은 비트마스킹 과정을 통해 값을 저장하고, 중복해서 계산하지 않는 것이 포인트 입니다.

 

 

 

아래는 정답코드입니다.

구조체 벡터때문에 복잡해보이지만 굉장히 간단한 논리입니다. 천천히 확인해 보세요!

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef struct MyStruct
{
	int time;
	vector <int> prefer;

}val;
val arr[501];
int n;
int dp[501];

int solved(int num) {

	if (dp[num] != 0) return dp[num];


	int maxed = 0;
	for (int i = 0; i < arr[num].prefer.size(); i++) {
		maxed = max(maxed, solved(arr[num].prefer[i]));
	}
	dp[num] = maxed + arr[num].time;
	return dp[num];
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> arr[i].time;
		int temp;
		while (1) {
			cin >> temp;
			if (temp == -1) {
				break;
			}
			arr[i].prefer.push_back(temp);
		}
	}
	/*
	for (int i = 1; i <= n; i++)
		cout << arr[i].prefer.size() << endl;
	*/

	for (int i = 1; i <= n; i++)
		cout << solved(i) << endl;

	return 0;
}

 

재귀를 쓰지않고 bfs를 활용해서도 답을 얻을 수 있습니다.

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int degree[501] = { 0, };
int N, n;
vector<int> vec[501];
int time[501], result[501];

void bfs() {
	queue<int> q;
	for (int i = 1; i <= N; i++) {
		if (degree[i] == 0) {
			q.push(i);
			result[i] = time[i];
		}
	}

	while (!q.empty()) {
		int front = q.front();
		q.pop();
		for (int i = 0; i < vec[front].size(); i++) {
			int e = vec[front][i];
			result[e] = max(result[e], result[front] + time[e]);
			if (--degree[e] == 0)
				q.push(e);
		}
		
	}
}


int main(void) {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> n;
		time[i] = n;
		while (1) {
			cin >> n;
			if (n == -1)	break;
			vec[n].push_back(i);
			degree[i]++;
		}
	}
	bfs();
	for (int i = 1; i <= N; i++)
		cout << result[i] << "\n";
	return 0;
}