2056 task
알고리즘(위상정렬)
1
2
3
4
5
6
7
1. Task 구조체를 선언하여, time : 현재 task가 걸리는 시간을 저장 / timeTaken : 현재까지 오는데 선행으로 필요한 작업을 수행하면서 걸리는 시간 중 가장 긴 시간 저장
next : 다음으로 이어지는 작업들을 저장
2. Task 구조체 배열을 앞에서부터 검사
-> 현재 task의 time과 timeTaken을 더해 temp에 저장.
-> 이어지는 작업들을 하나씩 검사 -> 이어지는 작업의 timeTaken보다 현재의 temp가 더 길면 temp를 저장
-> 검사가 끝나고 현재의 temp가 전체 temp중 가장 큰지 검사.(그냥 이어지는 작업 검사 끝나고 바로 maxTime 검사하면 됨)
3. 번호와 선행관계가 뒤죽박죽이 아닌, 선행 작업은 무조건 현재번호보다 앞에 있으므로 그냥 for문으로 앞에서부터 검사하면 된다.
평가.
1
선행관계가 똑바로 돼있어서 아주편하게 코딩함
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <vector>
#define MAX_TASK 10000
using namespace std;
typedef struct Task {
int time;
int timeTaken;
vector<int> next;
} Task;
Task task[MAX_TASK];
int numOfTask;
int minTimeComplete();
int main() {
cin >> numOfTask;
for (int i = 0; i < numOfTask; i++) {
cin >> task[i].time;
int numOfBefore;
cin >> numOfBefore;
for (int j = 0; j < numOfBefore; j++) {
int before;
cin >> before;
task[before-1].next.push_back(i);
}
}
cout << minTimeComplete();
}
int minTimeComplete() {
int maxTime = 0;
for (int i = 0; i < numOfTask; i++) {
int time = task[i].time + task[i].timeTaken;
for (int j = 0; j < task[i].next.size(); j++)
task[task[i].next[j]].timeTaken = task[task[i].next[j]].timeTaken > time ? task[task[i].next[j]].timeTaken : time;
maxTime = maxTime > time ? maxTime : time;
}
return maxTime;
}