[BOJ 백준] 2056번 작업

문제

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

2056번: 작업

접근

 모든 작업은 동시에 진행될 수 있고, 임의의 k번째 작업이 시작하기 위해 선행으로 완료되어야 하는 작업이 존재하는 경우가 있다. 예를 들면 4번 작업의 선행 작업으로 1번 작업이 요구된다면 4번 작업은 최소 1번 작업에 소요되는 시간 + 4번 작업에 소요되는 시간을 가진다. 다행히도 문제의 표현을 빌리자면 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 이는 문제 예제를 입력받으면서 동시에 k번째 작업을 완료하기 위한 최소 시간을 갱신해 나갈 수 있다는 뜻으로 다이나믹 프로그래밍(Dynamic Programming)을 통해 문제를 간단하게 해결했다.

 선행 작업에 대해 이해가 안 되는 사람들을 위해 좀 더 설명해 보자면, 예를 들어 7번째 작업을 위한 선행 작업으로 3, 5, 6번 작업을 요구한다고 생각해보자. 이 말은 7번 작업은 3번, 5번, 6번 작업이 끝나지 않는 한 시작할 수 없다는 뜻이다. 즉, 3, 5, 6번 작업 중 가장 마지막에 끝나는 작업의 시간 + 7번 작업에 소요되는 시간을 구하면 된다. 문제의 예제 입력 1을 참고하면 3번 작업은 9시간, 5번 작업은 12시간, 6번 작업은 19시간이 소요됨으로 7번 작업은 가장 늦게 끝나는 6번 작업의 19시간 + 4시간이 걸린다고 볼 수 있다. 최종적으로 정리해 보자면 필요로 하는 선행 작업 중 가장 늦게 끝나는 시간(선행 작업을 필요로 하지 않는다면 0) + 현재 작업의 소요 시간으로 갱신해 나간다고 볼 수 있다. 코드가 간단하니 코드를 보면 이해가 빠를 것이다.

코드

#include <iostream>

using namespace std;

int dp[10010] = {0};

int main() {
    int N, ans = 0;
    cin >> N;
    for(int i = 1; i <= N; i++) {
        int time, num, maxtime = 0, temp;
        cin>>time>>num;
        for (int j = 0; j < num; j++) {
            cin>>temp;
            if (dp[temp] > maxtime)
                maxtime = dp[temp];
        }
        dp[i] = maxtime + time;
        if (dp[i] > ans)
            ans = dp[i];
    }
    cout<<ans;
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study