백준 1516 게임 개발 - 위상정렬과 dp가 함께 쓰이는 문제(2)

문제 링크

www.acmicpc.net/problem/1516

1516번: 게임 개발

풀이 아이디어

백준 2056번 문제와 매우 비슷하다. 입출력 부분만 좀 달라졌다 보면 된다.  www.acmicpc.net/problem/2056

풀이는 여기를 보면 된다. hqjang.tistory.com/108

백준 2056 작업 - 위상정렬과 dp가 함께 쓰이는 문제

작업을 완료하기 위해 어떤 작업이 먼저 수행되어야 하는지를 파악해야 하므로

당연히 위상정렬 문제이다.

친절하게 각 줄의 두번째 int 값으로 indegree(먼저 수행되어야 하는 노드, 즉 조상노드의 개수)가 써져 있으므로

그대로 써먹으면 된다. (numOfancestor)

 

dp는 바로 이 '선행되는 조상노드의 실행 시간의 최댓값' 을 파악하기 위해 사용된다.

쉽게 예를 들어보겠다.

a라는 작업이 5분

b라는 작업이 10분

c라는 작업이 7분이 걸린다고 해보자.

이때 a는 반드시 b,c 작업이 끝나야 작업이 가능하다는 조건이 붙었다고 해보면

a를 끝낼 수 있는 최단 시간은 15분이다.

왜냐하면 b,c 중에서 더 작업 시간이 긴 b의 작업시간이 10분이기 때문이다.

(문제의 조건에 의해 b,c는 서로 연관이 없으므로 동시 수행이 가능)

코드에 해당하는 부분은 dp[next] = max(dp[next],dp[now]+t[next]); 이다.

next에 a가 들어가고 now 에 b,c가 들어가는 구조의 간단한 메모이제이션이다.

하지만 최댓값 기록을 위해,, 반드시 필요한 단계이다.

 

코드

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

int n;
int t[501],dp[501],numOfancestor[501];
vector<int> A[501];

int main(void){
    cin>>n;
    for(int i=1; i<=n; i++){
        int x;
        cin>>t[i];
        dp[i]=t[i];
        while(true){
            cin>>x;
            if(x==-1) break;
            else{
                A[x].push_back(i);
                numOfancestor[i]++;
            }
        }
    }

    queue<int> q;
    for(int i=1; i<=n; i++){
        if(numOfancestor[i]==0)
            q.push(i);
    }
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for(int i=0; i<A[cur].size(); i++){
            int next = A[cur][i];
            dp[next] = max(dp[next],dp[cur]+t[next]);
            numOfancestor[next]--;
            if(numOfancestor[next]==0)
                q.push(next);
        }
    }
    for(int i=1; i<=n; i++)
        cout<<dp[i]<<"\n";
}