틀렸던 접근 방식:
현재 작업이 끝나는 시간 = 선행해야하는 작업 중 가장 마지막 번호의 작업이 끝나는 시간 + 현재 작업에 필요한 시간
jobFinishedTime[i] = jobFinishedTime[requiredJob[i]] + requiredTime[i];
선행해야하는 작업 중 가장 마지막 번호의 작업이 가장 늦게 끝난다는 보장이 없으므로, 선행해야하는 모든 작업이 끝나는 시간에 대해 고려해야 한다
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 10001;
int N;
//index 1~N
vector<vector<int>> work(MAXN, vector<int>(1,0));
int time[MAXN];
int finish[MAXN] = { 0 };
int getFinishTime() {
int ret = 0;
for (int i = 1; i <= N; ++i){
int lastFinish = 0;
while (!work[i].empty()) {
lastFinish = max(lastFinish, finish[work[i].back()]);
work[i].pop_back();
}
finish[i] = lastFinish + time[i];
ret = max(ret, finish[i]);
}
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
for (int i = 1; i <= N; ++i) {
cin >> time[i];
int n;
cin >> n;
for (int j = 1; j <= n; ++j) {
int w;
cin >> w;
work[i].push_back(w);
}
}
cout << getFinishTime();
return 0;
}
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 10001;
int n;
int inDegree[MAXN] = { 0 };
int time[MAXN] = { 0 };
vector<int> child[MAXN];
//dp[node]
int dp[MAXN] = { 0 };
int topologySort() {
//pair<node>
queue<int> q;
for (int i = 1; i <= n; ++i)
if (inDegree[i] == 0) {
dp[i] = time[i];
q.push(i);
}
for (int i = 1; i <= n; ++i ){
if (q.empty()) break;
int parent = q.front();
q.pop();
for (int i = 0; i < child[parent].size(); ++i) {
int childnode = child[parent][i];
dp[childnode] = max(dp[childnode], dp[parent] + time[childnode]);
if (--inDegree[childnode] == 0) {
q.push(childnode);
}
}
}
int res = 0;
for (int i = 1; i <= n; ++i)
res = max(res, dp[i]);
return res;
}
int main(){
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> time[i];
cin >> inDegree[i];
for (int j = 0; j < inDegree[i]; ++j) {
int parent;
cin >> parent;
child[parent].push_back(i);
}
}
cout << topologySort();
return 0;
}