2056 task
์๊ณ ๋ฆฌ์ฆ(์์์ ๋ ฌ)
1. Task ๊ตฌ์กฐ์ฒด๋ฅผ ์ ์ธํ์ฌ, time : ํ์ฌ task๊ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ ์ ์ฅ / timeTaken : ํ์ฌ๊น์ง ์ค๋๋ฐ ์ ํ์ผ๋ก ํ์ํ ์์
์ ์ํํ๋ฉด์ ๊ฑธ๋ฆฌ๋ ์๊ฐ ์ค ๊ฐ์ฅ ๊ธด ์๊ฐ ์ ์ฅ
next : ๋ค์์ผ๋ก ์ด์ด์ง๋ ์์
๋ค์ ์ ์ฅ
2. Task ๊ตฌ์กฐ์ฒด ๋ฐฐ์ด์ ์์์๋ถํฐ ๊ฒ์ฌ
-> ํ์ฌ task์ time๊ณผ timeTaken์ ๋ํด temp์ ์ ์ฅ.
-> ์ด์ด์ง๋ ์์
๋ค์ ํ๋์ฉ ๊ฒ์ฌ -> ์ด์ด์ง๋ ์์
์ timeTaken๋ณด๋ค ํ์ฌ์ temp๊ฐ ๋ ๊ธธ๋ฉด temp๋ฅผ ์ ์ฅ
-> ๊ฒ์ฌ๊ฐ ๋๋๊ณ ํ์ฌ์ temp๊ฐ ์ ์ฒด temp์ค ๊ฐ์ฅ ํฐ์ง ๊ฒ์ฌ.(๊ทธ๋ฅ ์ด์ด์ง๋ ์์
๊ฒ์ฌ ๋๋๊ณ ๋ฐ๋ก maxTime ๊ฒ์ฌํ๋ฉด ๋จ)
3. ๋ฒํธ์ ์ ํ๊ด๊ณ๊ฐ ๋ค์ฃฝ๋ฐ์ฃฝ์ด ์๋, ์ ํ ์์
์ ๋ฌด์กฐ๊ฑด ํ์ฌ๋ฒํธ๋ณด๋ค ์์ ์์ผ๋ฏ๋ก ๊ทธ๋ฅ for๋ฌธ์ผ๋ก ์์์๋ถํฐ ๊ฒ์ฌํ๋ฉด ๋๋ค.
ํ๊ฐ.
์ ํ๊ด๊ณ๊ฐ ๋๋ฐ๋ก ๋ผ์์ด์ ์์ฃผํธํ๊ฒ ์ฝ๋ฉํจ
์ฝ๋
#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;
}