[C/C++] 백준 1005 - ACM Craft

[C/C++] 백준 1005 - ACM Craft

https://www.acmicpc.net/problem/1005

문제를 읽어보면 노드를 접근하는데 순서가 명시되어 있으므로 위상정렬을 사용해야 한다는 걸 확인 가능하다.

그리고 n이 크고 앞 건물의 시간을 계속 봐야하므로 값을 저장해두고 다시 사용하는 DP를 적용하면 시간을 줄일 수 있다.

DP 점화식은 dp[i] = i번째 노드의 자식 dp값 중 제일 큰 거 + 자기 건설 시간이고

구현 방식은 dfs로 위상정렬을 하면서 dp값을 갱신해서 저장하고 이미 방문한 정점은 dp값이 갱신되었으므로 dp값만 바로 읽어오도록 구현했다.

#include #include #include #include #include using namespace std; int n, k, w, a, b; bool visit[1001]; int arr[1001][1001]; int time[1001]; int dp[1001]; vector order; int t[501]; void print() { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) cout << arr[i][j] << " "; cout << "

"; } return; } int dfs(int idx) { int next, temp = 0; if (!visit[idx]) visit[idx] = true; for (int i = 1; i<= n; i++) { next = arr[idx][i]; if (!visit[next] && next) temp = max(temp, dfs(next)); else if (visit[next] && dp[next]) temp = max(temp, dp[next]); } return dp[idx] = temp + time[idx]; } int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int test; cin >> test; for (int h = 0; h < test; h++) { cin >> n >> k; for (int i = 1; i <= 1000; i++) { visit[i] = false; time[i] = dp[i] = 0; for (int j = 1; j <= 1000; j++) arr[i][j] = 0; } for (int i = 1; i <= n; i++) cin >> time[i]; for (int i = 1; i <= k; i++) { cin >> a >> b; arr[b][a] = a; } cin >> w; for (int i = 1; i <= n; i++) { if (!visit[i]) dfs(i); } cout << dp[w] << "

"; } return 0; }

전형적인 위상정렬 문제라 위상정렬을 처음 접하거나 연습하는 분들에게 좋은 문제인 듯 하다.

위상정렬은 dfs말고도 큐로도 구현이 가능하니 둘다 연습해보는 것도 좋을 거 같다.

from http://lts96.tistory.com/17 by ccl(A) rewrite - 2021-10-31 18:26:22