[알고리즘/백준] 2056: 작업

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

1. 문제 접근

 

• N개의 작업이 있고, 각각의 작업은 선행 작업이 있을 수 있다.
• 한 번에 하나의 작업만 수행할 수 있고,각 작업은 걸리는 시간이 주어진다.
• 선행 작업이 모두 끝난 뒤에야 해당 작업을 수행할 수 있다.
• 모든 작업을 완료하는 데 걸리는 최소 시간을 구하는 문제.

 

 

위상 정렬 + DP를 조합해서 풀 수 있다.

 

위상 정렬을 수행하면서 dp를 같이 수행한다..!

dp[i] = i번 작업을 끝마치는 데까지 걸리는 시간

점화식 : dp[next] = max(dp[next], dp[curr] + time[next])

 

마지막으로, dp[1] ~ dp[n] 중 가장 큰 값이 모든 작업을 완료하는데 걸리는 시간이다.

2. 코드

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int n;

    std::cin >> n;

    std::vector<int> time(n + 1);
    std::vector<int> indegree(n + 1);
    std::vector<std::vector<int>> graph(n + 1);
    std::vector<int> dp(n + 1);

    int count;
    for (int i = 1; i <= n; ++i)
    {
        std::cin >> time[i] >> count;
        while (count--)
        {
            int pre;
            std::cin >> pre;
            graph[pre].push_back(i);
            indegree[i]++;
        }
    }

    std::queue<int> queue;

    for (int i = 1; i <= n; ++i)
    {
        if (indegree[i] == 0)
        {
            queue.push(i);
            dp[i] = time[i];
        }
    }
    while (!queue.empty())
    {
        const int cur = queue.front();
        queue.pop();
        for (const int& next : graph[cur])
        {
            --indegree[next];
            dp[next] = std::max(dp[next], dp[cur] + time[next]);
            if (indegree[next] == 0)
            {
                queue.push(next);
            }
        }

        std::cout << cur;
    }
    int result = -1;
    for(const int& time : dp)
    {
        result = std::max(result, time);
    }

    std::cout << result;
}