[BOJ 1005] ACM Craft

🔗Link

문제
풀이(dfs) 풀이(위상 정렬)

💡Idea

현재 건물까지 짓는 시간은, 사전에 지어야 하는 건물들의 시간들 중 최댓값과 현재 건물을 짓는데 걸리는 시간의 합이다. 현재 건물과 다음 건물 사이의 짓는 데 걸리는 시간에 대한 점화식은 다음과 같겠다.

• times[i]: 건물 i를 짓는데 걸리는 시간
• dp[i]: 사전 건물들을 짓고 현재 것물을 짓는데 걸리는 시간
• dp[nxt] = max(dp[cur]) + times[nxt])

dp배열을 채우는 순서는 위상 정렬을 사용해도 괜찮고, dfs를 사용해도 괜찮겠다.

🔑Code

DFS

#include <bits/stdc++.h>
using namespace std;

int dfs(int cur, const vector<int> (&adj)[1001], int *times, int* dp){
    // 현재 건물까지 짓는 시간을 안다면 바로 리턴
    if(dp[cur] != -1) return dp[cur];

    // 모른다면 계산
    dp[cur] = 0;
    for(int nxt: adj[cur]){
        dp[cur] = max(dp[cur], dfs(nxt, adj, times, dp));
    }
    dp[cur] += times[cur];
    
    return dp[cur];
}

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

    int T;
    cin >> T;
    while(T--){
        int N, K, W, X, Y;
        int times[1001] = {0}, dp[1001];
        fill(dp, dp+1001, -1);
        vector<int> adj_reverse[1001];
        
        // 1. input
        cin >> N >> K;
        for(int i = 1; i <= N; i++){
            cin >> times[i];
        }
        for(int i = 0; i < K; i++){
            cin >> X >> Y;
            adj_reverse[Y].emplace_back(X);
        }
        cin >> W;

        // 3. 정답 출력
        cout << dfs(W,adj_reverse,times,dp) << '\n';
    }

    return 0;
}

위상 정렬

#include <bits/stdc++.h>
using namespace std;

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

    int T;
    cin >> T;
    while(T--){
        int N, K, W, X, Y;
        int times[1001] = {0}, dp[1001] = {0};
        int indegree[1001] = {0};
        fill(dp, dp+1001, -1);
        vector<int> adj[1001];
        queue<int> Q;
        
        // 1. input
        cin >> N >> K;
        for(int i = 1; i <= N; i++){
            cin >> times[i];
        }
        for(int i = 0; i < K; i++){
            cin >> X >> Y;
            adj[X].emplace_back(Y);
            indegree[Y]++;
        }
        cin >> W;

        // 2. 첫 건물 queue에 넣기
        for(int i = 1; i <= N; i++){
            if(indegree[i] == 0) Q.emplace(i);
            dp[i] = times[i]; // 첫 건물들은 본인 걸리는 시간이 최종 시간
        }

        // 3. 지을 수 있는 건물 지으면서 dp 배열 채우기
        while(!Q.empty()){
            int cur = Q.front(); Q.pop();

            for(int& nxt: adj[cur]){
                if(--indegree[nxt] == 0) Q.emplace(nxt);
                dp[nxt] = max(dp[nxt], dp[cur] + times[nxt]);
            }
        }

        // 3. 정답 출력
        cout << dp[W] << '\n';
    }

    return 0;
}

🗨️ Side Notes

목적	올바른 선언
배열 전달	int* arr
배열 전달 (C 스타일)	int arr[]
읽기 전용	const int* arr
크기까지 보존	int (&arr)[1001]
크기 + 읽기 전용	const int (&arr)[1001]