[ BOJ 백준 2056번 - 작업 ] 해설 및 코드

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

 

목적

선행 관계가 있는 모든 작업을 완료하기 위해 필요한 최소 시간을 구하자.

 

접근법

1. "K번 작업에 대해 선행 관계에 있는 작업들의 번호는 모두 1 이상 (K-1) 이하이다." 라는 조건으로 그래프든 위상정렬이든 다 필요 없다. n크기의 배열만 앞에서부터 차곡차곡 채워나가자.

2. a[i]는 i번째 작업의 완료시간으로, 선행 작업들의 완료시간 중 최대값과 i번째 작업의 소요시간을 더한다.

 

#include<bits/stdc++.h>
#define N 10001
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
 
int n, a[N], ans=0;
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    f(i, 1, n) {
        cin >> a[i];
        int cnt; cin >> cnt;
        int mx=0;
        while (cnt--) {
            int tmp; cin >> tmp;
            mx = max(mx, a[tmp]);
        }
        a[i] += mx;
        if (ans < a[i])ans = a[i];
    }
    cout << ans;
    return 0;
}

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.