[백준] 1005번: ACM craft / C++

✏️ 문제 링크

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

1005번: ACM Craft

 

 

✏️ 문제 설명 (더보기 클릭 👆🏻)

 

✏️ 문제 풀이

기본 위상정렬과 BFS 섞은 문제이다...!

 

👇🏻 위상정렬에 대한 설명 👇🏻

https://yabmoons.tistory.com/409

[ 백준 2252 ] 줄 세우기 (C++)

 

위의 코드를 바탕으로 dp를 추가해주면 되는데 각 dp의 칸은 "건물 i를 짓는데 걸리는 최소 시간이다!"

최소 시간이라고하면 앞에 모든 스텝이 끝나야하니 앞의 스텝중 가장 큰 값과 건물 i를 더해야한다. 

 

for(int i=0; i<vec[node].size(); i++){
   int nxt=vec[node][i];
   dp[nxt]=max(dp[nxt], dp[node]+spent[nxt]);
   entry[nxt]--;
   if(entry[nxt]==0){
   q.push(nxt);
   }
}

 

✏️ 문제 코드

#include <bits/stdc++.h>

using namespace std;
using pii=pair<int, int>;
int main(){
    int T; cin>>T;
    
    while(T--){
        
        int N, K, W; 
        cin>>N>>K;
        vector<long> spent(N+1, 0); 
        vector<int> vec[N+1];
        vector<int> entry(N+1, 0);
        vector<long> dp(N+1, 0);
        
        for(int i=1; i<=N; i++) cin>>spent[i];
        for(int i=0; i<K; i++){
            int a, b; cin>>a>>b;
            entry[b]++;
            vec[a].push_back(b);
        }
        cin>>W;
        
        queue<int> q;
        for(int i=1; i<=N; i++){
            if(entry[i]==0) {q.push(i); dp[i]=spent[i];}//node, step
        }
        while(!q.empty()){
            int t=q.front(); q.pop();
            int node=t;
            for(int i=0; i<vec[node].size(); i++){
                int nxt=vec[node][i];
                dp[nxt]=max(dp[nxt], dp[node]+spent[nxt]);
                entry[nxt]--;
                if(entry[nxt]==0){
                    q.push(nxt);
                }
            }
        }
        
        cout<<dp[W]<<"\n";
        
    }
    return 0;
}

 

 

 

 ⭐ if feedback and question : comment please⭐