[백준] 2056번: 작업 / C++

✏️ 문제 링크

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

2056번: 작업

 

 

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

 

✏️ 문제 풀이

2021.10.03 - [Algorithm 💫/알고리듬(thm) 공부 🌱] - [백준] 1005번: ACM craft / C++

위 문제를 해결했다면 동일한 방식!

 

✏️ 문제 코드

#include <bits/stdc++.h>

using namespace std;
#define MAX 10001
#define INF 987654321
vector<int> spent(MAX, 0);
vector<int> entry(MAX, 0);
vector<int> vec[MAX];
vector<int> dp(MAX, 0);
int main(){
    int N;cin>>N;
    //time, priority works, 아 내앞에 있는 번호들이 주어진다. 
    
    for(int i=1; i<=N; i++){
        cin>>spent[i]>>entry[i];
        for(int j=0; j<entry[i]; j++){
            int w; cin>>w;
            vec[w].push_back(i);
        }
    }
    queue<int> q; 
    for(int i=1; i<=N; i++){
        if(entry[i]==0) {q.push(i); dp[i]=spent[i];}
    }
    
    while(!q.empty()){
        int t=q.front(); q.pop();
        for(int i=0; i<vec[t].size(); i++){
            int nxt=vec[t][i]; 
            entry[nxt]--;
            dp[nxt]=max(dp[nxt], dp[t]+spent[nxt]);
            if(entry[nxt]==0) q.push(nxt);
        }
    }
    
    int ans=*max_element(dp.begin(), dp.begin()+(N+1));
    cout<<ans<<"\n";
    return 0;
}

 

 

 

 ⭐ if feedback and question : comment please⭐