[백준] 1516번: 게임 개발 / C++

✏️ 문제 링크

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

1516번: 게임 개발

 

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

 

✏️ 문제 풀이

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

2021.10.04 - [Algorithm 💫/알고리듬(thm) 공부 🌱] - [백준] 2056번: 작업 / C++

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

 

✏️ 문제 코드

#include <bits/stdc++.h>

using namespace std;
#define MAX 501
#define INF 987654321

vector<int> entry(MAX, 0);
vector<int> dp(MAX, 0);
vector<int> vec[MAX];
vector<int> spent(MAX, 0);
int main(){
    
    int N; cin>>N;
    for(int i=1; i<=N; i++){
        cin>>spent[i];
        int b; 
        while(true){
            cin>>b;if(b==-1)break;
            entry[i]++;
            vec[b].push_back(i);
        }
    }
    queue<int> q; 
    for(int i=1; i<=N; i++){
        if(!entry[i]){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]) q.push(nxt);
            
        }
    }
    
    for(int i=1; i<=N; i++) cout<<dp[i]<<"\n";
    
    return 0;
}

 

 

 

 ⭐ if feedback and question : comment please⭐