백준 1516번 게임 개발

< 백준 1516번 게임 개발 - 마포 코딩박 >

사용한 알고리즘: DP

 N개의 건물들에 대해, 해당 건물이 지어지는 시간과, 그 건물을 짓기 위해 먼저 지어져야할 건물들의 정보가 입력으로 주어집니다. 각 건물들이 완성되는데까지 필요한 최소 시간을 구하는 문제입니다.
 사실 위상정렬로 풀리는 문제이지만, 저는 DP로 풀었습니다.

문제풀이는 다음과 같습니다.

(1) (코드 10~11)
 'dp[x] : x 를 완공시키는데까지 필요한 최소 시간' 이라고 설정했습니다.

(2) (코드 13~25)
 dp 를 계산하는 함수를 만들어 주었습니다.
 a 라는 건물을 완공시키기 위한 최소 시간은, ( a 건물을 짓는 시간 + a 건물 이전에 지어져야 할 건물들의 완공시간 중 최대값 ) 입니다.

	#include <bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	int N, M;
	// arr[i] : i 전에 지어야 하는 건물
	set<int> arr[501];
	// num[i] : i 건물 짓는 시간
	ll num[501];
	// dp[x] : x 가 완공될때 까지 총 시간
	ll dp[501];
	ll dfs(int a){
	ll &temp = dp[a];
	if(temp!=0) return temp;
	// 기본적으로 자신을 짓는 시간은 필요하다
	temp += num[a];
	// a 건물보다 선행되어 지어져야하는 건물들의 완공시간 중 최대
	ll BeforeBuilding = 0LL;
	for (auto pre : arr[a])
	BeforeBuilding = max(BeforeBuilding,dfs(pre));
	temp += BeforeBuilding;
	return temp;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	for (int i = 1; i <= N; ++i){
	int ww;
	cin >> ww;
	num[i] = ww;
	while(1){
	int pre;
	cin >> pre;
	if(pre == -1) break;
	arr[i].insert(pre);
	}
	}
	for (int i = 1; i <= N; ++i)
	cout << dfs(i) << '\n';
	return 0;
	}

view raw BOJ 1516.cpp hosted with ❤ by GitHub