[C++] 백준 1005 ACM craft

문제 링크

---

www.acmicpc.net/problem/1005

1005번: ACM Craft

접근 방법

---

 일단 문제를 보자마자 떠오른 것은 DP를 사용해야겠다는 것이다. 처음 top-down방식으로 해결하였으나, 재귀가 깊어져서 인지 메모리 제한에 걸렸다.  그래서 bottom-up방식을 사용하여 다시 해결했다.

 

동적계획법을 사용하는 핵심 코드이다.

for (int i = 0; i < map[now].size(); i++) {
  int next = map[now][i];
  if (--indegree[next] == 0) {
  	q.push(next);
  }
  dp[next] = max(dp[next], dp[now] + buildtime[next]);
}

예를 들어 a를 짓기 위해 b와 c 두 건물이 모두 지어져야 한다면, b와 c둘 중 짓는대 까지 걸리는 시간 중 큰 값을 사용하여 현재 건물을 짓는 시간을 더하여 갱신 해주었다. 이 부분만 잘 이해한다면 크게 어려울 것은 없을 것이다.

 

소스 코드

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

int buildtime[1001];
int dp[1001];
int indegree[1001];
vector<int> map[1001];
int t, n, k, dest;

void init() {

	memset(buildtime, 0, sizeof(buildtime));
	memset(dp, 0, sizeof(dp));
	memset(indegree, 0, sizeof(indegree));
	for (int i = 0; i <= n; i++) {
		map[i].clear();
	}

	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> buildtime[i];
	}
	for (int i = 0; i < k; i++) {
		int a, b;
		cin >> a >> b;
		map[a].push_back(b);
		indegree[b]++;
	}
	cin >> dest;
}

int solve(int dest) {

	int result = 0;

	queue <int> q;
	for (int i = 1; i <= n; i++) 
		if (indegree[i] == 0) {
			q.push(i);
			dp[i] = buildtime[i];
		}

	while (!q.empty()) {
		
		int now = q.front();
		q.pop();

		if (now == dest) {
			result = dp[now];
			break;
		}

		for (int i = 0; i < map[now].size(); i++) {
			int next = map[now][i];
			if (--indegree[next] == 0) {
				q.push(next);
			}
			dp[next] = max(dp[next], dp[now] + buildtime[next]);
		}
	}

	return result;
}

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

	cin >> t;

	while (--t >= 0) {
		init();
		cout << solve(dest) << "\n";
	}
}

개발 환경 : VS2019

질문, 지적 환영합니다!