(2637) 장난감 조립

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

단계별로 풀어보기

40단계(동적 계획법 3) 7번째

 

 

 

사이클이 없는 방향 그래프(DAG)에서 DP를 적용하는 문제다.

DP를 적용하기 위해서는 방향성에 거스르지 않도록 하위 단계부터 갱신하는 것이 중요하다.

따라서 위상 정렬 알고리즘과 결합해야 한다. 위상 정렬로 나온 결과 순서대로 DP를 계산하면 된다.

 

 

 

#include <iostream>
#include <queue>
using namespace std;
typedef pair<int,int> p;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n >> m;
  
  queue<int> q;
  vector adj(n+1, vector<p>());
  vector<int> indegree(n+1), dp(n+1), order;
  vector<bool> isbase(n+1, true);
  
  while(m--){
    int x, y, k;
    
    cin >> x >> y >> k;
    
    adj[x].push_back({k,y});
    indegree[y]++;
    isbase[x]= false;
  }
  
  for(int i=1;i<=n;i++){
    if(!indegree[i]){
      q.push(i);
    }
  }
  
  while(!q.empty()){
    int now= q.front();
    q.pop();
    
    order.push_back(now);
    
    for(p next:adj[now]){
      if(!--indegree[next.second]){
        q.push(next.second);
      }
    }
  }
  
  dp[n]= 1;
  for(int now:order){
    for(p next:adj[now]){
      dp[next.second]+= dp[now]*next.first;
    }
  }
  
  for(int i=1;i<=n;i++){
    if(isbase[i])  cout << i << " " << dp[i] << "\n";
  }
  
  return 0;
}